[Tutor] recursion and power sets

[alice]

<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 
adding x to each element.
</ tim>

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

<python>
 def powset(seq):
     if seq:
         head, tail = seq[:1], seq[1:]
         for smaller in powset(tail):
             yield smaller
             yield head + 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>