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