Fast powerset function

Jyotirmoy Bhattacharya jmoy.matecon at
Fri Jul 13 19:38:24 CEST 2007

On Jul 13, 6:34 pm, Carsten Haese <cars... at> 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([])
       for t in do_recursive(S):
           yield t
           yield t|x
   return do_recursive(s.copy())

More information about the Python-list mailing list