Fast powerset function

[Carsten Haese]

On Fri, 2007-07-13 at 17:38 +0000, Jyotirmoy Bhattacharya wrote:
> On Jul 13, 6:34 pm, Carsten Haese <cars... at uniqsys.com> 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
> >             yield subset.union(set([x]))
> >
> Your recursive_powerset is buggy--it generates too many sets. The loop
> over the elements of s is unnecessary. Here is one alternative:
> 
> def recursive_powerset(s):
>    def do_recursive(S):
>        if not S:
>            yield set([])
>            return
>        x=set(S.pop())
>        for t in do_recursive(S):
>            yield t
>            yield t|x
>    return do_recursive(s.copy())

Right you are. Note however that x=set(S.pop()) should be
x=set([S.pop()]) for this to run.

Forget everything I've said about timing comparisons, the correct
recursive implementation is actually faster than the iterative
implementation I was testing.

-Carsten