29 Jan 2004 (updated 3 Feb 2004 at 07:05 UTC)
»
I did this code a few weeks ago, but I still fascinated the simple and clean it looks in python with iterators:
def powerset(set):
for size in range(len(set)+1):
for subset in powersetOfSize(set, size):
yield subset
def powersetOfSize(set, size):
if size > 1:
for i in range(len(set) - (size-1)):
for subset in powersetOfSize(set[i+1:], size-1):
yield [set[i]] + subset
elif size == 1:
for i in set:
yield [i]
else:
yield []
As you may have guessed, given a set of elements as a python list, this code allows you to iterate through the elements of its power set in increasing set size order.
You may be thinking this guy is mad if he thinks that iterator recursive code is simple. But hey! If you look an example, and think how you would write that in another programming language, you will probably agree with me.
The promised clarification example:
>>> l = [1, 2, 3]
>>> for i in powerset(l):
... print i
...
[]
[1]
[2]
[3]
[1, 2]
[1, 3]
[2, 3]
[1, 2, 3]