[Tutor] recursion and power sets

[Tim Peters]

[alice]
> Ouch! I think I've injured my brain on this one.
> I'm beginning to think recursion is not so cool after all.....
>
> I was trying to write a function that would take a set -
> represented as a list with non repeating elements - and return
> the power set, so given:
>
> [1,2,3]
>
> it should return:
>
> [[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]
>
> After much general confusion, this is what I eventually came up with:

... [code to generate in order of size] ...

> This gives the subsets in a simmilar order to the one in which I
> would find them if I was doing it by hand, but its kind of difficult
> to think about, so I thought about it a bit more and came up with:

... [code that looks at the integers in range(2**len(set)), and
     picks apart the bits to select subsets] ...

> Even though this algorithm gives the subsets in a completely
> different order to the way I'd normally find them by hand, I'm
> guessing its closer to the "canonical" algorithm for finding power
> sets than my recursive attempt, am I right?

There isn't really a canonical way -- "whatever works" is fine.

> or is there a third, completely different way of doing this?

Oh, many <wink>.  There are 2**N pieces in the result, and the factorial of
that many ways to order them.  Here's a particularly concsise way of
generating the powerset:

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

Given that, then

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

prints

[]
[1]
[2]
[1, 2]
[3]
[1, 3]
[2, 3]
[1, 2, 3]

That's close to "canonical" in the sense that it closely follows a natural
way of *thinking* about the problem.  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.  Well, each element of the powerset of T either does or doesn't
contain x.

If it doesn't contain x, it must be an element of the powerset of S too.
Conversely, each element of the powerset of S is also an element of the
powerset of T.

On the other hand, if it does contain x, then if we took x out of it we'd
also be left with an element of the powerset of S; and adding x to an
element of the powerset of S must conversely give an element of the powerset
of T.

Put it all together, and the powerset of T is the powerset of S, plus the
powerset of S fiddled by adding x to each element.

That's how the code above works:

    if S isn't empty:
        pick the first element and call it "head"
        call the rest of S "tail"
        for each element e of the powerset of tail:
            one element of the powerset of S is e
            another is e plus head

Now that's a naturally recursive way of thinking about the problem (we think
about how the powerset of a set is related to the powerset of a smaller
set), so it leads to simple recursive code.  Your

> I'm beginning to think recursion is not so cool after all.....

comes from trying to force a recursive solution out of a non-recursive way
of thinking about the problem.  That is indeed painful <wink>.