Fast powerset function

Evan Klitzke evan at yelp.com
Fri Jul 13 20:13:37 CEST 2007


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?
> Thanks
> -Arash

Here's a much simpler (and faster) solution I got from a coworker:

s = range(18)
result = []

l = len(s)
for i in range(2**l):
    n = i
    x = []
    for j in range(l):
        if n & 1:
            x.append(s[j])
        n >>= 1
    result.append(x)

print result


-- 
Evan Klitzke <evan at yelp.com>



More information about the Python-list mailing list