[Tutor] recursion and power sets
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.
light bulb turning on above alice's head
head, tail = seq[:1], seq[1:]
for smaller in powset(tail):
yield head + smaller
for s in powset([1, 2, 3]):
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