P4.3.5Power sets
The power set of a set \(S\), \(P(S)\), is the set of all subsets of S, including the empty set and \(S\) itself. For example,
P((1,2,3)) = (), (1), (2), (3), (1,2), (1,3), (2,3), (1,2,3)
Write a Python program which uses a generator to return the power set of a given set.
Hints: convert your set into an ordered sequence such as a tuple. For each item in this sequence return the power set formed from all subsequent items, inclusive and exclusive of the chosen item. Don't forget to convert the tuples back to sets after you're done.
Show solution
Here is one possible solution:
def _powerset(s):
""" A generator yielding the power set of the items in the sequence s. """
if len(s) <= 1:
yield s # The singleton set
yield () # The empty set
else:
# Loop over the elements in the power set formed from all the items
# after the first in s and yield them with and without this first one.
for item in _powerset(s[1:]):
yield (s[0],) + item
yield item
def powerset(s):
""" A generator returning all the subsets of the set s. """
return set((frozenset(_s) for _s in _powerset(tuple(s))))
S = {'a', 'b', 'c'}
P = powerset(S)
print(P)
# An alternative, nicer way to print the powerset: sorted by cardinality of
# subsets and then by subset elements (assuming they can be ordered)
print(tuple(sorted((tuple(sorted(s)) for s in P), key = lambda s: (len(s),s))))
Note that we have to use frozensets if they are to be items in a set.