[Tutor] recursion and power sets

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

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>

light bulb turning on above alice's head

 def powset(seq):
     if seq:
         head, tail = seq[:1], seq[1:]
         for smaller in powset(tail):
             yield smaller
             yield head + smaller
         yield []

 for s in powset([1, 2, 3]):
     print s

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

pieces of puzzle slowly falling into place

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

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"!

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)

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_.
Anyway, thanks for guiding me from the first apparent solution to the 
beautiful one! Now I have to go and think about them 

More information about the Tutor mailing list