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 2n 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