Creating all possible ways of a boolean array of s

问题:

I need to be able to create a boolean array of one combination and run it through a program to see if it works. If not then I dispose of it and go to the next combination. My issue is that I don't know how to create this array because n can be equal anywhere from 1-1000. So I was planning on using Integer.toBinaryString but that won't work due to its too big when it gets to past 32. Any help would be greatful.

Thanks!

回答1:

The "accepted answer" states that

Tested and this will work for high values of n, such as 10000 and so on.

But this is incorrect.

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 loop forever repeating the first 2^31 combinations since i will overflow and will never reach Math.pow(2, n). You can easily test 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");
            }
        }
    }

Code above will indefinitely print i exceeded Integer.MAX_VALUE However this can easily be corrected 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);
    }
}

回答2:

I've found the answer to your problem on another SO question, and I've 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 for high values of n, such as 10000 and so on.