JAVAの0と1ビットのすべての可能な順列を得る方法

Question

長さ3のビットの順列の出力が必要です（0と1の初期の組み合わせがランダムに生成されるので順序は関係ありません）：

[0,0,0]

[0,0,1]

[0,1,0]

[0,1,1]

[ 1,0 、0]

[1,0,1]

[1,1,0]

[1,1,1]

私が行っているが、それはそれあるようです重複している可能性のある並べ替えが表示されていません。

'

ArrayList<Item> itemsAvailable = new ArrayList<Item>(); 
    ArrayList<Integer>bits = new ArrayList<Integer>(); 
    ArrayList<ArrayList<Integer>> tried = new ArrayList<ArrayList<Integer>>(); 

    itemsAvailable.add(new Item(5,4)); 
    itemsAvailable.add(new Item(12,10)); 
    itemsAvailable.add(new Item(8,5)); 

    System.out.println("itemsAvailable: " + itemsAvailable); 

    Random r = new Random(); 

    //permutations 
    for(int i = 0; i < Math.pow(2,itemsAvailable.size()); i++){ 
     //Generate random bits 

     for(int j = 0; j < itemsAvailable.size(); j++){ 
      int x = 0; 

      if (r.nextBoolean()) 
       x = 1; 

      bits.add(x); 

     } 


     System.out.println("Added to bits #" + (i+1) + ": " + bits); 

     bits = new ArrayList<Integer>(); 
    } 

' 私は得られる出力である：これは私のコードである

、ビット＃1に追加：[0、0、1]

ビット＃2に追加されました：[1、1、0] - 複製

ビット＃3に追加されました：[1、0、1]

0ビット＃6に追加dupicate

- [0,0,0]：[1、1、[0、0、1]

はビット＃5に追加：ビット＃4に追加

したがって、私は8を得ることができる方法

をdupicate - [0,0,0]：＃8 [1、1、1]

追加されたビットに： - 0]

が＃7ビットに追加dupicateビットがランダムに生成されるときの異なる順列はありますか？助けてください。

ありがとうございます。

Answer 1

あなたは組み合わせがあなただけのような何かを行うことができ、その後数えるよりも他に何もないことを認識している場合： Integer.toBinaryString（I）バイナリ

iとして値を出力します

public static void main(String[] args) { 
    for (int i = 0; i < 8; i++) { 
     System.out.println(String.format("%3s", Integer.toBinaryString(i)).replace(' ', '0')); 
    } 
} 

と

String.Formatの（ "％3sの"、Integer.toBinaryString（I））。置き換える（」」、 '0'）

は、左側に先行ゼロが追加されるため、よりよく読むことができます。

Answer 2

これについて簡単な方法があります。符号なしの2の補数では、これらのビットはバイナリで表すものと考える：

• [0,0,0] - > 0
• [0,0,1] - > 1
• [0,1 、0] - > 2
• ...
• [1,1,1] - > [7

だから、これらすべての順列を取得する簡単な方法は次のとおりです。

8から来ないこと

for (int i = 0; i < 8; ++i) { 
    bits.add(i); 
} 

？

このテクニックは、Javaのint型が署名されているため、最大31ビットで動作します（上記のコードでは基本的にunsignedと扱いますが、それより低い数字で動作します）。

intの代わりにlongを使用して2^63までバンプすることができます。すべてを列挙するだけで、64の長さにすることができます。それを超えて、別のアプローチが必要です。しかし、2^64ロングは、8バイト/ロングで約1.5e11ギガバイトです。そのため、より複雑なアルゴリズムが必要となる前に、RAMを使い果たしてしまいます。