Generating all combinations of size 1 to n (bitsets)

user_11853015 0
Viewed 62

There is a lot of quick methods on stack overflow that generate all the combination of bitsets of size k.

Ex:

combos(4,3) = {1110,1101,1011,0111}

However, is there a quick way to calculate all combos for sizes 1 to n?

Ex:

allCombos(4) = 
{
  1: {0001, 0010, 0100, 1000}
  2: {0011, 0101, 1001, 0110, 1010, 1100}
  3: {0111, 1011, 1101, 1110}
  4: {1111}
}

Of course, I can just call combos(4, i) for i from 1 to 4. However, I want to take advantage of the following fact:

For each bitset X in combos(4, i), we can set exactly one bit from bitset X from 0 to 1.

For example, 0011 is in combos(4,2) which generates {1011, 0111} in combos(4,3) since the 1st and 2nd most significant bits are 0's.

EDIT: here is my current way of accomplishing this:

def combos(set_, k):
    return map(sum, itertools.combinations(set_, k)) # take combos of 1, 2, 4, 8 ... and the sums to get bitset back

def allCombos(n):
    ret = {}
    bitset = set([2**i for i in range(n)]) # generates 1, 2, 4, 8 ...
    for k in range(1,n+1):
        ret[k] = combos(bitset, k)
    return k
bitset combinations python
1 Answers

As Frank Yellin points out your "shortcut" is probably not really that helpful. The only way I think you could slightly improve the time of this calculation is to recognize that if we flip each bit in each bitset in combos(n,i) we get the bitset combos(n,n-i). You could create a very simple and fast function that would take in a set of bitsets and return a set with the opposite bitset for each. For example if given combos(4,1) which is {0001,0010,0100,1000}, it would output {1110,1101,1011,0111} which is combos(4,3). This would cut your runtime roughly in half.

user_129476940
Related