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

12,376

Solution 1

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

Solution 2

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

Solution 3

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).

Solution 4

Implemented it in a function-

static public ArrayList<boolean[]> getBoolArr(int length) {
        int numOptions = 1 << length;
        ArrayList<boolean[]> finalArray = new ArrayList<boolean[]>();
        for(int o=0;o<numOptions;o++) {
            boolean[] newArr = new boolean[length];
            for(int l=0;l<length;l++) {
                int val = ( 1<<l ) & o;
                newArr[l] = val>0;
            }
            finalArray.add(newArr);
        }
        return finalArray;
    }

example of usage-

ArrayList<boolean[]> res = getBoolArr(2); //2 is your length, change it however you want.

Solution 5

This is how I did it in Java

public class NbitsStrings {
    int[] arrA;
    public static void main(String[] args) throws java.lang.Exception {
        Scanner input = new Scanner(System.in); //Input the Number Of bits you want.
        int n = input.nextInt();
        NbitsStrings i = new NbitsStrings(n);
        i.nBits(n);
    }
    public NbitsStrings(int n) {
        arrA = new int[n];
    }
    public void nBits(int n) {
        if (n <= 0) {
            StringBuilder builder = new StringBuilder();
            for (int value : arrA) {
                builder.append(value);
            }
            String text = builder.toString();
            System.out.println(text);
        } else {
            arrA[n - 1] = 0;
            nBits(n - 1);
            arrA[n - 1] = 1;
            nBits(n - 1);
        }
    }
}
Share:
12,376

Related videos on Youtube

snotyak
Author by

snotyak

Updated on June 04, 2022

Comments

  • snotyak
    snotyak almost 2 years

    For example, if I wanted all binary strings of length 3 I could simply declare them like this:

    boolean[] str1 = {0,0,0};
    boolean[] str2 = {0,0,1};
    boolean[] str3 = {0,1,0};
    boolean[] str4 = {0,1,1};
    boolean[] str5 = {1,0,0};
    boolean[] str6 = {1,0,1};
    boolean[] str7 = {1,1,0};
    boolean[] str8 = {1,1,1};
    

    What is the most efficient way to generate all possibly binary strings of length N into a boolean array?

    I don't necessarily need the most efficient method, just one that's fairly efficient and easy for me to multithread.

    EDIT: I should note that I will be storing them all in an ArrayList, if that matters.

  • snotyak
    snotyak over 12 years
    Didn't work for me. If I use low numbers as length I get out of bounds exceptions. If I use large numbers I get 1-digit outputs. I don't understand all of the << and whatnot. Care to explain?
  • snotyak
    snotyak over 12 years
    I'm liking this method. I'll wait for some more though.
  • Alon Amir
    Alon Amir over 12 years
    try again, it works. I've put the code inside a function so there is no place for mistakes (see update). let me know if you have any problems. '<<' and '&' are bit operators. see fredosaurus.com/notes-cpp/expressions/bitops.html for explanation (it's c++ but works for java too).
  • user314104
    user314104 over 12 years
    @chickeneaterguy: Since you said that you want to multithread it, one (or two) trivial improvement(s) I'd make here are: 1) Move the prints out of the loops, and 2) change the type of i to an AtomicInteger (making necessary adjustments). #2 could then be adapted trivially to a multithreaded implementation. Not sure how much you'll gain this way, as the code block here is tiny. A better way of dividing the work on threads might be to split the ranges on i for each thread.
  • snotyak
    snotyak over 12 years
    @user314104 : I did it. It's fast. I did it with an arraylist instead but I used your method. Thanks!
  • Anurag Awasthi
    Anurag Awasthi about 7 years
    Only it will fail at n=31