Fastest way to generate all binary strings of size n into a boolean array?
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);
}
}
}
Related videos on Youtube
snotyak
Updated on June 04, 2022Comments
-
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 over 12 yearsDidn'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 over 12 yearsI'm liking this method. I'll wait for some more though.
-
Alon Amir over 12 yearstry 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 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 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 about 7 yearsOnly it will fail at n=31