4

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
Peabrain
  • 519
  • 2
  • 12
  • I honestly don't think your "shortcut" is particularly efficient. For any particular element in "list `n`", there are `n` elements in "list `n-1`" that can have one bit set to give that element. If you're using `itertools.combinations`, it's really efficient. – Frank Yellin Nov 25 '21 at 17:47
  • itertools.combinations requires a set as input. My input will be an integer (a bitset). Right now, I have to convert my bitset to an actual python set, call itertools.combinations and then convert that set back into a bitset. Too inefficient. – Peabrain Nov 26 '21 at 02:25
  • https://stackoverflow.com/questions/70119046/itertools-combinations-on-bitset – Peabrain Nov 26 '21 at 02:35
  • 1
    @martineau. I don't think this is a duplicate. This user isn't trying to create subsets. He wants numbers with that many bits set, which is a slightly different problem. – Frank Yellin Nov 26 '21 at 04:55
  • "quick way" is rather subjective - how quick is your current approach? What does the code for that current approach look like? – Mortz Nov 26 '21 at 08:30
  • if you are looking on some specific ordering, from `ì` to `ì+1`, then you asking to get the nodes between two consecutive levels. So rearrange the "combinations" using a tree structure – cards Nov 26 '21 at 09:38
  • @Mortz I added what I am currently doing. It defeats the purpose of using bitsets (somewhere else in my code) when I have to convert them into sets of powers of 2, and use `itertools.combinations` to get what I want. – Peabrain Nov 27 '21 at 14:53

1 Answers1

0

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.

Eric T-M
  • 93
  • 5