$$\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 testHere'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