Fast powerset function

Carsten Haese carsten at uniqsys.com
Fri Jul 13 15:34:41 CEST 2007


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





More information about the Python-list mailing list