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.

Improve this question

7 Answers 7

Reset to default
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();
    }
Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

I'm liking this method. I'll wait for some more though.
@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 : I did it. It's fast. I did it with an arraylist instead but I used your method. Thanks!
Only it will fail at n=31
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

Improve this answer

Comments

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

Improve this answer

Comments

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.
Improve this answer

2 Comments

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?
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).
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);
        }
    }
}
Improve this answer

Comments

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

Improve this answer

Comments

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.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.