On 13 Jul 2007 02:25:59 -0700, Paul Rubin wrote > Antoon Pardon <[EMAIL PROTECTED]> writes: > > On 7/12/07, Arash Arfaee <[EMAIL PROTECTED]> 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 -- http://mail.python.org/mailman/listinfo/python-list