Fast powerset function

[Carsten Haese]

On Fri, 2007-07-13 at 08:15 -0400, I wrote:
> [...]
> def recursive_powerset(s):
>     if not s: yield set()
>     for x in s:
>         s2 = s - set([x])
>         for subset in recursive_powerset(s2):
>             yield subset
>         for subset in recursive_powerset(s2):
>             yield subset.union(set([x]))
> [...]

Pardon the soliloquy, but now that I'm a bit more awake, I realize that
this is unnecessarily slow due to the duplicate invocation of the
recursive call. Changing it thusly cuts the run time roughly in half:

def recursive_powerset(s):
    if not s: yield set()
    for x in s:
        s2 = s - set([x])
        for subset in recursive_powerset(s2):
            yield subset
            yield subset.union(set([x]))

However, this doesn't change the fact that the iterative method blows
the recursive method out of the water.

-- 
Carsten Haese
http://informixdb.sourceforge.net