Fastest way to generate all binary strings of size n into a boolean array?

Here's some code to generate a truth table... (works for only for 32 bits because of array size limits ( you can change the size variable to whatever and store booleans as 1/0 if you want):

int size = 3;
    int numRows = (int)Math.pow(2, size);
    boolean[][] bools = new boolean[numRows][size];
    for(int i = 0;i<bools.length;i++)
    {
        for(int j = 0; j < bools[i].length; j++)
        {
            int val = bools.length * j + i;
            int ret = (1 & (val >>> j));
            bools[i][j] = ret != 0;
            System.out.print(bools[i][j] + "\t");
        }
        System.out.println();
    }

Example: If you need of length 4, then you must have 2^4 = 16 different arrays.

You can use this simple Java code to generate all arrays:

for (int i=0; i < (Math.pow(2,4)); i++) {
        System.out.println(Integer.toBinaryString(i));
}

The output of this:

0 1 10 11 100 101 110 111 1000 1001 1010 1011 1100 1101 1110 1111

If you do not care about having all the permutations at once, a smart thing to do is to allocate no memory beforehand and simply write an algorithm which calculates the strX you want, on-the-fly.

Advantages of doing this:

• You can handle arbitrarily large number of permutations without having to allocate all permutations
• Since the algorithm stores nothing, it is thread friendly
• You only pay for the rows that you want. For example, if n=1,000, but you only need a few of the permutations, this will be much faster and require a tiny fraction of memory (only one row worth)

To get you started, the algorithm's interface can look something like this:

boolean[] getRow( int rowNumber, int nItems )

So you would call getRow(5,3) to get str5 returned from the function. I leave it up to you to implement the details (it's not hard).