9

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
  • 3,709
  • 6
  • 35
  • 52

7 Answers7

6

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();
    }
LazyCubicleMonkey
  • 1,213
  • 10
  • 17
  • I'm liking this method. I'll wait for some more though. – snotyak Dec 04 '11 at 08:54
  • @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. – user314104 Dec 04 '11 at 09:05
  • @user314104 : I did it. It's fast. I did it with an arraylist instead but I used your method. Thanks! – snotyak Dec 04 '11 at 10:03
  • Only it will fail at n=31 – Anurag Awasthi Mar 22 '17 at 17:33
4

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

Community
  • 1
  • 1
xsiraul
  • 414
  • 1
  • 5
  • 16
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).

kfmfe04
  • 14,936
  • 14
  • 74
  • 140
1

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);
        }
    }
}
devDeejay
  • 5,494
  • 2
  • 27
  • 38
1

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.
Alon Amir
  • 4,913
  • 9
  • 47
  • 86
  • 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 Dec 04 '11 at 08:52
  • 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 http://www.fredosaurus.com/notes-cpp/expressions/bitops.html for explanation (it's c++ but works for java too). – Alon Amir Dec 04 '11 at 09:01
0

javascript implementation relevant to duplicate Question https://stackoverflow.com/questions/42591231/calculate-all-possible-combinations-of-n-off-on-elements.

As with all numbers, there is a relationship between sets of numbers, where once the pattern is recognized, addition can be used to derive the relationships between sets of numbers at specific indexes within an array sets.

let [N, n1, n2, n3] = [0, 1, 9, 89];

let [res, max] = [Array(Array(3).fill(N)), Math.pow(2, 3)];

for (let i = 1, curr; i < max; i++) {

  if ([1, 3, 5, 7].some(n => n === i)) {
    N += n1;
  }

  if ([2, 6].some(n => n === i)) {
    N += n2;
  }

  if (i === max / 2) {
    N += n3;
  }

  curr = Array.from(String(N), n => +n);

  if (N < 100) {
    while (curr.length < 3) {
      curr.unshift(n1 - 1);
    }
  }

  res.push(curr);

}

console.log(res);
Community
  • 1
  • 1
guest271314
  • 1
  • 15
  • 104
  • 177
0

This is how I implemented it in Scala 

def combinations(n: Int): List[List[Int]] = {
 val numbers = scala.math.pow(2, n).toInt 
 //Convert each to binary equivalent 
 def toBinary(decimal: Int, binary: List[Int]): List[Int] = {
  if (decimal <= 0)
    return le(binary)
  toBinary(decimal / 2, (decimal % 2) :: binary)
 }
 // Size alignment 
 def le(binary: List[Int]):List[Int]=
  {
    if(binary.length!=n) le(0::binary) else binary
  }
 def getCombinations(n: Int, list: List[List[Int]]): List[List[Int]] = {
  if (n < 0)
    return list
  getCombinations(n - 1, toBinary(n, Nil) :: list)
 }
 getCombinations(numbers - 1, Nil)
}

Sample output:

  • combinations(2) //List(List(0, 0), List(0, 1), List(1, 0), List(1, 1))
  • combinations(3) //List(List(0, 0, 0), List(0, 0, 1), List(0, 1, 0), List(0, 1, 1), List(1, 0, 0), List(1, 0, 1), List(1, 1, 0), List(1, 1, 1))

Thanks to my friend James A.

Jemal Ahmed
  • 11
  • 2