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!

sorry my bad, n is the number of spots needed to be in the boolean array — Fischerk12, Nov 19 '14 at 02:21
Have you considered using an [ArrayList](https://docs.oracle.com/javase/7/docs/api/java/util/ArrayList.html)? ArrayList for example allows you to add an indefinite number of booleans. It is like a self extending array. — Perry Monschau, Nov 19 '14 at 02:22
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. — Fischerk12, Nov 19 '14 at 02:25
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](https://docs.oracle.com/javase/6/docs/api/java/math/BigInteger.html)? — Perry Monschau, Nov 19 '14 at 02:29
n is the number of spots in the array. I need all the combinations of the array — Fischerk12, Nov 19 '14 at 02:33
Will [BigInteger](https://docs.oracle.com/javase/6/docs/api/java/math/BigInteger.html) work for you? Try looking into it. — Perry Monschau, Nov 19 '14 at 02:35
It might but I am not exactly sure how to implement it into my solution — Fischerk12, Nov 19 '14 at 02:53
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)) — user1207177, Nov 19 '14 at 02:59
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. — Fischerk12, Nov 19 '14 at 03:01

score 5 · Accepted Answer · answered Jun 07 '17 at 15:21

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

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) — Koen, Nov 10 '20 at 13:28

score 3 · Answer 2 · edited May 23 '17 at 12:02

3

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.

edited May 23 '17 at 12:02

Community

1
1

answered Nov 19 '14 at 03:07

victorantunes

1,141
9
20

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. – Fischerk12 Nov 19 '14 at 03:10
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. – victorantunes Nov 19 '14 at 03:15
`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 – SGal Jun 07 '17 at 15:34
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... – Koen Nov 10 '20 at 13:35

Win Myo Htet · Answer 3 · 2019-06-17T08:51:33.383

0

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

edited Jun 17 '19 at 08:51

answered Jun 17 '19 at 08:36

Win Myo Htet

5,377
3
38
56

Instead of using string, you can generate this directly: https://github.com/passbook/BinarySequencer – Sentry.co Jul 04 '20 at 17:14

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

3 Answers3

Linked

Related