Thursday, 25 April 2013

Powersets

While looking over purported Google interview questions, I found one that was just 'write some code to make powersets'. It turns out that the powerset of a set $S$ is the set of all its subsets (including itself):
$$\mathcal{P}( S ) = \{s \subseteq S \}$$
My first attempt at a solution was an ugly iterative algorithm that used lists to represent sets. An hour or so of tinkering led me to this lazy, recursive solution using python's built in set type (which is a hash table and thus has constant-time lookups):
def subsetsOfLength(S, l):
    ''' Return a generator of all subsets of S that are of length l.

        Note: this function uses recursion, so l must be less than your python implementation's
        recursion limit (default 1000 for C Python).
    '''

    if l > len(S):
        pass # Return a length-zero iterator when subsets larger than S itself are requested.
    
    elif l == 0:
        yield set() # The empty set is the only set of length 0
        
    elif l == 1:
        for s in S:
            yield {s} # Just yield each element if only length-one elements are required
        
        # This clause isn't strictly required, but it saves len(S) redundant function calls that would all
        # return the empty set (to be unioned with x)
        
    else:
        S = S.copy() # Avoid mangling the original parameter
        
        while S:
            x = {S.pop()} # x is a set containing a single, arbitrary element from S

            # Yield the union of x with every possible subset of S\{x} (that has
            # the correct length to make the union be length l):
            for y in subsetsOfLength(S, l-1):
                yield x.union(y)

def powerset(S):
    ''' Return a generator for the powerset (the set of all [non-strict] subsets) of some set S
    '''

    for l in xrange(len(S)+1):
        for x in subsetsOfLength(S, l):
            yield x


if __name__ == '__main__': # Module Test/Demo
    print 'Length 3 subsets of S=[1, 5]'
    print '\n'.join((str(x) for x in subsetsOfLength(set(range(1, 6)), 3)))
    print
    print 'Powerset of S=[1, 3]'
    print '\n'.join((str(x) for x in powerset(set(range(1, 4)))))
    print
    print 'The length of the powerset of S with |S| = 12 is %d' % sum(1 for _ in (powerset(set(range(12)))))
        # This could be calculated a-priori, as 2^|S|, but that wouldn't be a test
Here's the test output:

Length 3 subsets of S=[1, 5]
set([1, 2, 3])
set([1, 2, 4])
set([1, 2, 5])
set([1, 3, 4])
set([1, 3, 5])
set([1, 4, 5])
set([2, 3, 4])
set([2, 3, 5])
set([2, 4, 5])
set([3, 4, 5])

Powerset of S=[1, 3]
set([])
set([1])
set([2])
set([3])
set([1, 2])
set([1, 3])
set([2, 3])
set([1, 2, 3])

The length of the powerset of S with |S| = 12 is 4096

No comments:

Post a Comment

About Me

Melbourne, Victoria, Australia
I'm hard at work on an MSc in Physics at the University of Melbourne, my research topic is 'building nano-scale neural networks'. In my (limited) spare time I tinker with 3D printing, electronics and programming.