AsinglePANCAKE AsinglePANCAKE - 3 months ago 23
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?

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
Comments