Wie bekomme ich alle möglichen Permutationen für 0 und 1 Bits in JAVA

Question

Ich brauche die Ausgabe der Permutation für Bits der Länge 3 zu sein (die Reihenfolge spielt keine Rolle, wie die ursprüngliche Kombination von 0 und 1 zufällig generiert wird):

[0,0,0]

[0,0,1]

[0,1,0]

[0,1,1]

[ 1,0 0]

,

[1,0,1]

[1,1,0]

[1,1,1]

Ich habe getan, aber es scheint, dass es sind Duplikate und einige mögliche Permutationen werden nicht angezeigt, ich bin mir nicht sicher, warum. Dies ist mein Code:

'

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>(); 
    } 

'

Die Ausgabe, die ich erhalten ist:

Added to Bits # 1: [0, 0, 1]

Zu Bits # 2 hinzugefügt: [1, 1, 0] - Duplikat

Hinzugefügt zu Bits # 3: [1, 0, 1]

an Bits addiert # 4: [0, 0, 1]

Hinzu Bits # 5: [0, 0, 0] - dupicate

Hinzu Bits # 6: [1, 1, 0] - dupicate

hinzugefügt Bits # 7: [1, 1, 1]

hinzugefügt Bits # 8: [0, 0, 0] -

Deshalb dupicate wie kann ich erhalten 8 verschiedene Permutationen wie die Bits zufällig generiert werden? Bitte helfen Sie.

Vielen Dank.

Answer 1

Wenn Sie sind sich bewusst, dass die Kombinationen ist nichts anderes, als zu zählen, dann können Sie nur, wie etwas tun:

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

wo Integer.toBinaryString (i) den i-Wert als binäre

drucken

und

String.format ("% 3-Fettsäuren", Integer.toBinaryString (i)). ersetzen (‘‘, '0')

wird führende Nullen nach links hinzufügen, damit Sie es besser lesen können

Answer 2

Es gibt einen einfacheren Weg, dies zu tun. Denken Sie an, was diese Bits binär darstellen, in Ergänzung unsigned Zweierkomplement:

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

So ist die einfache Möglichkeit, alle diese Permutationen zu bekommen ist:

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

Wo kommt das 8 kommen aus? Es ist nur 2^3, da Sie die Länge 3 wollten.

Diese Technik funktioniert für bis zu 31 Bits, da Java Int-Typ signiert ist (während die oben im Grunde behandelt es als unsigned, die bei diesen niedrigeren Zahlen funktioniert).

Sie können es bis zu 2^63 mit langen anstelle von Int stoßen, und Sie können 64-Länge erhalten, indem Sie einfach alle Longs. Darüber hinaus benötigen Sie einen anderen Ansatz. aber 2^64 Longs, bei 8 Bytes pro Long, ist etwa 1,5e11 Gigabyte - so haben Sie nicht mehr RAM, bevor Sie einen komplexeren Algorithmus benötigen.