CODEWITHSUNDEEP
javarandompermutationbit
mina_mz
mina_mz

Reputation: 59

How to get all possible permutations for 0 and 1 bits in JAVA

I need the output of permutation for bits of length 3 to be (the order doesn't matter as the initial combination of 0 and 1 is generated randomly):

[0,0,0]

[0,0,1]

[0,1,0]

[0,1,1]

[1,0,0]

[1,0,1]

[1,1,0]

[1,1,1]

I have done but it seems that there are duplicates and some possible permutation are not being displayed which I'm not sure why. This is my 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>();
    }

'

The output that I obtained is:

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

Added to bits #2: [1, 1, 0] - duplicate

Added to bits #3: [1, 0, 1]

Added to bits #4: [0, 0, 1]

Added to bits #5: [0, 0, 0] - dupicate

Added to bits #6: [1, 1, 0] - dupicate

Added to bits #7: [1, 1, 1]

Added to bits #8: [0, 0, 0] - dupicate

Therefore how can I obtain 8 different permutations as the bits are generated randomly? Please help.

Thank you.

Upvotes: 1

Views: 1682

Answers (2)

yshavit
yshavit

Reputation: 43391

There's an easier way to go about this. Think of what these bits represent in binary, in unsigned two's complement:

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

So the easy way to get all these permutations is:

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

Where does that 8 come from? It's just 2^3, since you wanted length 3.

This technique works for up to 31 bits, since Java's int type is signed (whereas the above basically treats it as unsigned, which works at those lower numbers).

You can bump it up to 2^63 by using long instead of int, and you can get 64-length by just enumerating all longs. Beyond that, you'll need a different approach; but 2^64 longs, at 8 bytes per long, is about 1.5e11 gigabytes -- so you'll have run out of RAM way before you need a more complex algorithm.

Upvotes: 5

ΦXocę 웃 Пepe&#250;pa ツ
ΦXocę 웃 Пepe&#250;pa ツ

Reputation: 48278

If you are aware that the combinations is nothing else than counting then you can just do something like:

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

where Integer.toBinaryString(i) will print the i value as binary

and

String.format("%3s", Integer.toBinaryString(i)).replace(' ', '0')

will add leading zeros to the left so you can read it better

Upvotes: 3

Related Questions