# Fast powerset function

Carsten Haese carsten at uniqsys.com
Fri Jul 13 14:15:38 CEST 2007

```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

```