[Tutor] recursion and power sets

alice RobinHood42 at clickta.com
Mon Mar 8 04:48:26 EST 2004

```<email>
<tim>
Suppose we already had the powerset of a set S, and wanted the powerset of the
set T consisting of S and a new element x.

The powerset of T is the powerset of S, plus the powerset of S fiddled by
</ tim>

<image>
light bulb turning on above alice's head
</image>

<python>
def powset(seq):
if seq:
for smaller in powset(tail):
yield smaller
else:
yield []

for s in powset([1, 2, 3]):
print s
</python>

<alice>
This is one of them iterator-thingy-ma-bobs, isn't it?  hmmmm.....
</alice>

<sound>
pieces of puzzle slowly falling into place
</sound>

<tim>
There isn't really a canonical way -- "whatever works" is fine.....
Here's a particularly concsise way.....
</tim>

<alice>
I kind of thought that, with respect to algorithms, "canonical" and "most
concise" were the same thing? Surely python programmers, of all people, are
not of the attitude that: "whatever works is fine"!
</alice>

<tim>
That's close to "canonical" in the sense that it closely follows a natural way
of *thinking* about the problem.  (we think about how the powerset of a set
is related to the powerset of a smaller set)
</tim>

<alice>
In retrospect it does seem like a very natural way of thinking about the
problem. I wonder why I didn't see it myself?
Perhaps because I knew that I _could_ find the subsets in order of smallest to
largest, I felt that somehow I _should_.
hmmmm...
Anyway, thanks for guiding me from the first apparent solution to the
beautiful one! Now I have to go and think about them
iterator-thingy-ma-bobs.....
</alice>
</email>

```