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
Hi, good post. I have been wondering about this issue,so thanks for posting.
Comment by ApplyCreditCards — May 29, 2009 2:34:40 AM | # - re
The article is ver good. Write please more
Comment by JaneRadriges — Jun 14, 2009 3:12:18 AM | # - re
Doesn't work for the empty sequence.
Comment by Jason — Oct 20, 2009 3:14:06 PM | # - re
Tnx for the code! A minor modification, so that it works for the empty sequence, too:
def powerset(seq):
"""
Returns all the subsets of this set. This is a generator.
"""
if seq:
for item in powerset(seq[1:]):
yield [seq[0]]+item
yield item
else:
yield seq
Comment by Saso — Jan 4, 2010 1:40:26 PM | # - re