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

Question

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!

Saunders

what is n? The length of the array? – Hermes

sorry my bad, n is the number of spots needed to be in the boolean array – Saunders

Have you considered using an ArrayList? ArrayList<Boolean> for example allows you to add an indefinite number of booleans. It is like a self extending array. – Compulsion

My main issue is that I don't know how to create all possible combinations, such as for a size 3 the first combination would be 000, then the next would be 001, next 010 or something along that nature. – Saunders

So... n is the number of digits in the boolean array, and you want to create an array of all boolean numbers up until n digits? Is that right? Have you considered using BigInteger? – Compulsion

n is the number of spots in the array. I need all the combinations of the array – Saunders

Will BigInteger work for you? Try looking into it. – Compulsion

It might but I am not exactly sure how to implement it into my solution – Saunders

You probably don't want to generate all of the combinations up front because there are 2^n of them (2^100 ~10^301 (10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376 to be precise)) – Gravure

Well I am a creating one combination, testing it to see if it works, then keeping it if it does and then testing the next one to see if it has a better outcome. – Saunders

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

Volatile

In case anybody is interested in a bit of extra performance (like I needed), I used this in the loop to shave about 40% of the time boolean[] boolArray = new boolean[n]; long mask = 1; for (int j = 0; j < n; j++) { boolArray[j] = (i & mask) > 0; mask <<= 1; } (Oh, do note that I used longs instead of ints or bigintegers, this means it will work for n <= 63, also the speed comparison was compared to the example using integers and strings, so there will be an even better speedup compared to the BigInteger version (but of course there will be the n limit in this case) – Ferwerda

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

Belgium

See I saw that but wouldn't it cause issues since i have to go to 1000 different spots in the array so I would need something with 1000 bytes. – Saunders

Yes, my bad. I'm actually getting OutOfMemoryError's when I try higher numbers for n. In that case, you'd simply have to create 2^n arrays with a size of [n]. I've updated my answer. – Belgium

for (int i = 0; i < Math.pow(2, n); i++) when n > 31 will loop forever as the integer i will overflow as assertTrue(Integer.MAX_VALUE + 1 == Integer.MIN_VALUE) See my answer for rectified implementation – Volatile

I highly doubt you tested it with 10000, not only will this solution loop forever, but also 2^10000 is such a big number that I'm not sure if any computer ever counted towards that... – Ferwerda

Answer 3

I know that the there is a Java tag. I just want to add my swift 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)
    }

Hail

Instead of using string, you can generate this directly: github.com/passbook/BinarySequencer – Tricia