Fast powerset function

[Jyotirmoy Bhattacharya]

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())