Most elegant way to generate possible boolean combinations

Question

What is the most elegant way to generate the possible boolean combinations given the max number of booleans you want?

Ex :

bool(1) -> [false], [true]
bool(2) -> [false, false], [false, true], [true, false], [true, true]
...

This is my current implementation:

public static List<Boolean[]> bool(int n) {
    return IntStream.range(0, (int) Math.pow(2, n))
                    .mapToObj(i -> StringUtils.leftPad(Integer.toBinaryString(i), n, '0').chars().mapToObj(c -> c != '0').toArray(Boolean[]::new))
                    .collect(Collectors.toList());
}

However I'm not satisfied with the fact that I use integers, then map to binary with StringUtils.leftPad and the map that returns a Boolean[] instead of a boolean[].

Is there a nicer way to do it in a one-liner using the Stream API?

Answer 1

Try this:

boolean[] bitSetToArray(BitSet bs, int width) {
    boolean[] result = new boolean[width]; // all false
    bs.stream().forEach(i -> result[i] = true);
    return result;
}

List<boolean[]> bool(int n) {
    return IntStream.range(0, (int)Math.pow(2, n))
        .mapToObj(i -> bitSetToArray(BitSet.valueOf(new long[] { i }), n))
        .collect(toList());
}

The key is that BitSet has a stream() method on it that returns a stream of indexes of the one-bits. This can be used to set true values into a boolean[]. Also note that (like Bubletan) it's possible to have a List<boolean[]> instead of List<Boolean[]>. That is, a list of array of primitive boolean values instead of a list of array of boxed Boolean values. (This is because arrays are of reference types and thus can be used as a type argument.)

Finally, thanks to Bubletan, whose solution I augmented by adding bitSetToArray().

UPDATE

srborlongan asked in a comment whether the following might be better:

List<boolean[]> bool(int n) {
    return IntStream.range(0, (int)Math.pow(2, n))
        .mapToObj(i -> new long[] { i })
        .map(BitSet::valueOf)
        .map(bs -> bitSetToArray(bs, n))
        .collect(toList());
}

It does have the advantage of being less dense. After all, this isn't code golf, APL, or Perl where the goal seems to be to write something the most terse way possible. Code that's less dense is often, but not always, easier to read and understand.

There are some nuances in this case though, I think. The "obj" being emitted by the mapToObj stage is long[], which is inferred to be the parameter type of BitSet::valueOf. This in turn affects overload resolution! Unless you're already intimately familar with the BitSet API, you have to do a bit of type inference yourself to figure out what this is doing. So in this case it might be better to have a direct method call to BitSet.valueOf(long[]).

In terms of performance -- which is not always top priority -- I think that direct method calls probably perform better than a chain of map operations. Passing a value through an additional stream operation involves perhaps two method calls, plus the overhead of the Lambda Metafactory calls for the additional lambda(s). In addition, direct method calls are likely more easily optimized by the JIT, and inlined, than passing values through the stream. But I haven't verified any of this.

Answer 2

If it has to be Streams:

public static List<boolean[]> bool(int n) {
    return IntStream.range(0, 1<<n).mapToObj(
        i->IntStream.range(0, n)
            .collect(()->new boolean[n], (ba,j)->ba[j]=((i>>>j)&1)!=0,
            (x,y)->{throw new UnsupportedOperationException();})
      ).collect(Collectors.toList());
}

I left out the unused merge function for two boolean[] arrays, though it is possible to provide such function. But especially the inner Stream code is not a big win compared to a straight-forward loop:

public static List<boolean[]> bool(int n) {
    return IntStream.range(0, 1<<n).mapToObj(i-> {
        boolean[] ba=new boolean[n];
        for(int j=0; j<n; j++) ba[j]=((i>>>j)&1)!=0;
        return ba;
    }).collect(Collectors.toList());
}

Answer 3

Tried something. Doesn't use the Stream API for everything.. Though I don't think it's possible to create a boolean[] with it. Haven't used it much so I might be wrong.

public static List<boolean[]> bool(int n) {
    return IntStream.range(0, 1 << n)
            .mapToObj(i -> BitSet.valueOf(new long[] {i}))
            .map(bs -> {
                boolean[] a = new boolean[n];
                for (int i = 0; i < n; i++) {
                    a[n - i - 1] = bs.get(i);
                }
                return a;
            })
            .collect(Collectors.toList());
}

Answer 4

Only kind of a one-liner - and it gives you an Iterator not a List but it demonstrates the principle of counting up and rendering each bit of the count as a boolean.

public static Iterator<Boolean[]> bool(final int n) {
    return new Iterator<Boolean[]>() {
        final BigInteger max = BigInteger.ONE.shiftLeft(n);
        BigInteger next = BigInteger.ZERO;

        @Override
        public boolean hasNext() {
            return next.compareTo(max) < 0;
        }

        @Override
        public Boolean[] next() {
            Boolean[] b = new Boolean[n];
            for (int i = 0; i < n; i++) {
                b[i] = next.testBit(i);
            }
            next = next.add(BigInteger.ONE);
            return b;
        }

    };
}

OldCurmudgeon has no time for these new-fangled Stream thingies. They'll never catch on - its just a fad ... get off my lawn!! :)

My rather failed attempt at a Stream solution - I'm still not groking them:

private static Boolean[] asBooleanArray(BigInteger n) {
    int l = n.bitLength();
    Boolean[] b = new Boolean[l];
    for (int i = 0; i < l; i++) {
        b[i] = n.testBit(i);
    }
    return b;
}

    List<Boolean[]> bools = 
            Stream.<BigInteger>iterate(
                    BigInteger.ZERO, 
                    i -> i.add(BigInteger.ONE))
            .map(n -> asBooleanArray(n))
            .collect(Collectors.toList());

I'm having problems terminating an infnite Stream.