AsinglePANCAKE - 6 months ago 52

Python Question

If I've enumerated the powerset of the alphabet, for example, as 0,...,1<<26-1.

For a given number in that range, I want to know what all of its subsets are. I can do something a bit inefficient like:

`def find_subset_chain(subset):`

return [i for i in subset if i & subset == i]

In the event that I'm doing this for

Perhaps there exists a more number theoretic way to produce the list of subsets of a given element, a, of the powerset without having to iterate through every element up to a?

Answer

We can find the least significant set bit of a number as

```
n & -n
```

and we can use that to "count down" the subsets of a set represented as a bitmask by repeatedly clearing the least significant set bit and restoring all less-significant set bits from the original number:

```
def subsets(bitmask):
current = bitmask
while current:
yield current
lssb = current & -current # find least significant set bit
current &= ~lssb # clear least significant set bit
current |= bitmask & (lssb - 1) # restore less significant bits from original
yield current
```