AsinglePANCAKE - 1 year ago 108
Python Question

Subset chains within powerset in python

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 every element of the powerset, I can proceed backward from the element in question until I hit a subset, and then attach the stuff I've already figured out, but it happens to be the case that I want to do this for some select elements of the power set and not all of them.

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?

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):