Fast powerset function

[Carsten Haese]

On 13 Jul 2007 02:25:59 -0700, Paul Rubin wrote
> Antoon Pardon <apardon at forel.vub.ac.be> writes:
> > On 7/12/07, Arash Arfaee <Arash at ece.ucsb.edu> wrote:
> > > I need a powerset generator function. It's really slow with recursion. Does
> > > anybody have any idea or code(!!) to do it in an acceptable time?
> > My idea would be the following. ...
> > 3) let n range from 0 to 2 ** lng
> 
> That may help a little but my guess is the slowness comes from
> the size (2**n) of the power set.

That's true if by "a little bit" you mean "a lot." Observe:

"""
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]))

def nonrecursive_powerset(s):
    # Four lines of code hidden.
    # I want the OP to figure this out for himself.

import time

print "   N     Recursive Non-Recursive"
print "   - ------------- -------------"
for n in range(8):
    t1 = time.time()
    x = list(recursive_powerset(set(range(n))))
    t2 = time.time()
    x = list(nonrecursive_powerset(set(range(n))))
    t3 = time.time()
    print "%4d %12.6fs %12.6fs" % (n,t2-t1,t3-t2)
"""

Results:

   N     Recursive Non-Recursive
   - ------------- -------------
   0     0.000029s     0.000026s
   1     0.000027s     0.000028s
   2     0.000063s     0.000036s
   3     0.000379s     0.000067s
   4     0.004795s     0.000191s
   5     0.045020s     0.001054s
   6     0.633989s     0.013931s
   7    14.881078s     0.212958s

It is correct that a power set algorithm can never be truly fast because the
run time is exponential by definition, but the non-recursive (iterative)
method is still a lot faster than the recursive method.

-Carsten