A powerset generator in python

The powerset of a set is the set of all possible subsets of a set. i.e. for the list [1, 2, 3], the power set is [ [], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3] ]. [wikipedia has more].

Generators in Python a powerful concept, and allow you to have lists that you can generate as you go along. So you don't need to calculate all the items in a list before using them. As you can see from the example above, the number of elements in a powerset of a list is much larger than the number of elements in the original list. If there are n items in the original list, then there are 2ⁿ items in the powerset. For example, the powerset of a 5 element list has 32 items, the powerset of a 10 element list has 1,024 items and so forth. Since powersets are so large, generators are very helpful here, since you don't have to generate (and store) a 1,024 element list before doing your calculation. Here is a simple generator function in python that will return (or 'yield') all the lists in the powerset of a list.

def powerset(seq): """ Returns all the subsets of this set. This is a generator. """ if len(seq) <= 1: yield seq yield [] else: for item in powerset(seq[1:]): yield [seq[0]]+item yield item

Note: the code originally appeared on my old site

This entry is tagged: