Creating all possible paths of a boolean array of size n?

Question

I need to create a logical array from one combination and run it through a program to see if it works. If not, then I will get rid of it and move on to the next combination. My problem is that I do not know how to create this array, because n can be equal anywhere from 1 to 1000. Therefore, I planned to use Integer.toBinaryString, but this will not work due to its too large value when it will reach 32. Any help would be helpful.

Thanks!

Answer 1

The “accepted answer” says that

Tested, and this will work for large n values ​​such as 10000, etc.

But this is not true .

public static void main(String[] args) { final int n = 3; for (int i = 0; i < Math.pow(2, n); i++) { String bin = Integer.toBinaryString(i); while (bin.length() < n) bin = "0" + bin; char[] chars = bin.toCharArray(); boolean[] boolArray = new boolean[n]; for (int j = 0; j < chars.length; j++) { boolArray[j] = chars[j] == '0' ? true : false; } System.out.println(Arrays.toString(boolArray)); } } 

When n > 31 , it will cycle through the first 2 ^ 31 combinations, as i will overflow and never reach Math.pow(2, n) . You can easily check this with

 public static void main2(String[] args){ int n = 32; for (int i = 0; i < Math.pow(2, n); i++){ if (i == Integer.MIN_VALUE) { // i overflows System.out.println("i exceeded Integer.MAX_VALUE"); } } } 

The above code will endlessly print i exceeded Integer.MAX_VALUE However, this can easily be fixed using BigInteger or a similar data structure for looping. The code below will work for n <= Integer.MAX_VALUE

 public static void main(String[] args) { final int n = 32; BigInteger bi = BigInteger.ZERO; BigDecimal rows = new BigDecimal(Math.pow(2, n)); while (bi.compareTo(rows.toBigInteger()) < 0) { String bin = bi.toString(2);//Integer.toBinaryString(i); while (bin.length() < n) bin = "0" + bin; char[] chars = bin.toCharArray(); boolean[] boolArray = new boolean[n]; for (int j = 0; j < chars.length; j++) { boolArray[j] = chars[j] == '0' ? true : false; } System.out.println(Arrays.toString(boolArray)); bi = bi.add(BigInteger.ONE); } } 

Answer 2

I found the answer to your problem in another question fooobar.com/questions/978366 / ... and I adapted it for you:

 public class Foo { public static void main(String[] args) { final int n = 3; for (int i = 0; i < Math.pow(2, n); i++) { String bin = Integer.toBinaryString(i); while (bin.length() < n) bin = "0" + bin; char[] chars = bin.toCharArray(); boolean[] boolArray = new boolean[n]; for (int j = 0; j < chars.length; j++) { boolArray[j] = chars[j] == '0' ? true : false; } System.out.println(Arrays.toString(boolArray)); } } } 

Will produce:

 [true, true, true] [true, true, false] [true, false, true] [true, false, false] [false, true, true] [false, true, false] [false, false, true] [false, false, false] 

Tested and this will work with high n values ​​like 10000, etc.

Answer 3

I know there is a Java tag. I just want to add my quick code converted from Java to the answer.

  let SIZE = 4 let max = (pow(2, SIZE) as NSDecimalNumber).intValue; for i in 0..<max { var bin = String(i, radix: 2) while (bin.count < SIZE){ bin = "0" + bin } var boolArray = [Bool](); var count = 0 for ch in bin { boolArray.append(ch == "0") count = count + 1 } print(boolArray) }