Creating combinations of a BitSet

Question

Assume I have a Java BitSet. I now need to make combinations of the BitSet such that only Bits which are Set can be flipped. i.e. only need combinations of Bits which are set.

For Eg. BitSet - 1010, Combinations - 1010, 1000, 0010, 0000

BitSet - 1100, Combination - 1100, 1000, 0100, 0000

I can think of a few solutions E.g. I can take combinations of all 4 bits and then XOR the combinations with the original Bitset. But this would be very resource-intensive for large sparse BitSets. So I was looking for a more elegant solution.

So you want the powerset of a bitset? – Sweeper Aug 22 '19 at 08:44 — Sweeper, Aug 22 '19 at 08:44

Sweeper · Accepted Answer · 2019-11-18T08:48:30.400

It appears that you want to get the power set of the bit set. There is already an answer here about how to get the power set of a Set<T>. Here, I will show a modified version of the algorithm shown in that post, using BitSets:

private static Set<BitSet> powerset(BitSet set) {
    Set<BitSet> sets = new HashSet<>();
    if (set.isEmpty()) {
        sets.add(new BitSet(0));
        return sets;
    }
    Integer head = set.nextSetBit(0);
    BitSet rest = set.get(0, set.size());
    rest.clear(head);
    for (BitSet s : powerset(rest)) {
        BitSet newSet = s.get(0, s.size());
        newSet.set(head);
        sets.add(newSet);
        sets.add(s);
    }
    return sets;
}

Thanks a lot! Exactly what I needed :D – SSPdude Aug 23 '19 at 05:57 — SSPdude, Aug 23 '19 at 05:57

score 1 · Answer 2 · answered Nov 15 '19 at 14:12

You can perform the operation in a single linear pass instead of recursion, if you realize the integer numbers are a computer’s intrinsic variant of “on off” patterns and iterating over the appropriate integer range will ultimately produce all possible permutations. The only challenge in your case, is to transfer the densely packed bits of an integer number to the target bits of a BitSet.

Here is such a solution:

static List<BitSet> powerset(BitSet set) {
    int nBits = set.cardinality();
    if(nBits > 30) throw new OutOfMemoryError(
        "Not enough memory for "+BigInteger.ONE.shiftLeft(nBits)+" BitSets");
    int max = 1 << nBits;
    int[] targetBits = set.stream().toArray();
    List<BitSet> sets = new ArrayList<>(max);
    for(int onOff = 0; onOff < max; onOff++) {
        BitSet next = new BitSet(set.size());
        for(int bitsToSet = onOff, ix = 0; bitsToSet != 0; ix++, bitsToSet>>>=1) {
            if((bitsToSet & 1) == 0) {
                int skip = Integer.numberOfTrailingZeros(bitsToSet);
                ix += skip;
                bitsToSet >>>= skip;
            }
            next.set(targetBits[ix]);
        }
        sets.add(next);
    }
    return sets;
}

It uses an int value for the iteration, which is already enough to represent all permutations that can ever be stored in one of Java’s builtin collections. If your source BitSet has 2³¹ one bits, the 2³² possible combinations do not only require a hundred GB heap, but also a collection supporting 2³² elements, i.e. a size not representable as int.

So the code above terminates early if the number exceeds the capabilities, without even trying. You could rewrite it to use a long or even BigInteger instead, to keep it busy in such cases, until it will fail with an OutOfMemoryError anyway.

For the working cases, the int solution is the most efficient variant.

Note that the code returns a List rather than a HashSet to avoid the costs of hashing. The values are already known to be unique and hashing would only pay off if you want to perform lookups, i.e. call contains with another BitSet. But to test whether an existing BitSet is a permutation of your input BitSet, you wouldn’t even need to generate all permutations, a simple bit operation, e.g. andNot would tell you that already. So for storing and iterating the permutations, an ArrayList is more efficient.

Creating combinations of a BitSet

2 Answers2