## 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