# Re: Fast powerset function

Discussion in 'Python' started by Evan Klitzke, Jul 13, 2007.

1. ### Evan KlitzkeGuest

On 7/12/07, Arash Arfaee <> 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?
> Thanks
> -Arash

I thought that this was a really interesting question, so I wrote up a
solution that doesn't use recursion. I didn't test it a whole lot, but
I'm pretty sure it works -- let me know if there are any oversights or
if you can make any improvements ;-) Also, not sure if the line breaks
will be mangled by my mail client, so bear with me if there are any
errors.

def fact(n):
'''Factorial'''
r = 1
for i in xrange(1, n + 1):
r *= i
return r

def nCr(n, r):
'''Number of combinations of r items from n things'''
return fact(n) / (fact(r) * fact(n - r))

def get_combinations(slots, tokens):
'''A generator yielding combinations from slots of size tokens'''
maxcombos = nCr(len(slots), tokens)
for index in xrange(maxcombos):
token_copy = tokens
combo = []
for val in xrange(1, len(slots) + 1):
if not token_copy:
break
thresh = nCr(len(slots) - val, token_copy - 1)
if index < thresh:
combo.append(slots[val-1])
token_copy -= 1
else:
index -= thresh
yield tuple(combo)

def powerset(s):
'''Returns the powerset of s'''
pset = set()
for num_tokens in xrange(1, len(s)):
for combo in get_combinations(s, num_tokens):
# These two are special cases
return pset

if __name__ == '__main__':
print powerset((1, 2, 3, 4))

--
Evan Klitzke <>

Evan Klitzke, Jul 13, 2007

2. ### Antoon PardonGuest

On 7/12/07, Arash Arfaee <> 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?
> Thanks

My idea would be the following.

1) Turn your set into a list: lst

2) let lng be the number of elements.

3) let n range from 0 to 2 ** lng

4) now n represents subset as follows

consider n as a binary number
bit k is set in n <=> lst[k] is a member of the subset.

--
Antoon Pardon

Antoon Pardon, Jul 13, 2007

3. ### Paul RubinGuest

Antoon Pardon <> writes:
> On 7/12/07, Arash Arfaee <> 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.

Paul Rubin, Jul 13, 2007
4. ### Carsten HaeseGuest

On 13 Jul 2007 02:25:59 -0700, Paul Rubin wrote
> Antoon Pardon <> writes:
> > On 7/12/07, Arash Arfaee <> 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

Carsten Haese, Jul 13, 2007
5. ### Carsten HaeseGuest

On Fri, 2007-07-13 at 08:15 -0400, I 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
> for subset in recursive_powerset(s2):
> yield subset.union(set([x]))
> [...]

Pardon the soliloquy, but now that I'm a bit more awake, I realize that
this is unnecessarily slow due to the duplicate invocation of the
recursive call. Changing it thusly cuts the run time roughly in half:

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

However, this doesn't change the fact that the iterative method blows
the recursive method out of the water.

--
Carsten Haese
http://informixdb.sourceforge.net

Carsten Haese, Jul 13, 2007
6. ### Jyotirmoy BhattacharyaGuest

On Jul 13, 6:34 pm, Carsten Haese <> 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())

Jyotirmoy Bhattacharya, Jul 13, 2007
7. ### Carsten HaeseGuest

On Fri, 2007-07-13 at 17:38 +0000, Jyotirmoy Bhattacharya wrote:
> On Jul 13, 6:34 pm, Carsten Haese <> 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())

Right you are. Note however that x=set(S.pop()) should be
x=set([S.pop()]) for this to run.

Forget everything I've said about timing comparisons, the correct
recursive implementation is actually faster than the iterative
implementation I was testing.

-Carsten

Carsten Haese, Jul 13, 2007