Powersets of a list?

[Corran Webster]

In article <f9712f33.0105251051.4163a0ee at posting.google.com>, Walter
Vannini <walterv at jps.net> wrote:

> This also seems to do it:
> 
> def PowerSet2( PowerSetSoFar, element):
>     return [i+j for i in PowerSetSoFar for j in [ [], [element] ] ]
> 
> def PowerSet( set ):
>     return reduce (PowerSet2, set, [ [] ])
> 
> print PowerSet([1,2,3])

Refining this a bit and putting it into one function gives:

def PowerSet(list):
    PowerSetSoFar = [[]]
    for element in list:
        PowerSetSoFar += [i+[element] for i in PowerSetSoFar ]
    return PowerSetSoFar

which may be the best solution offered so far.

For MacPython 2.1 on a 400 Mhz B&W G3 running OS X, this is comparable
to or slightly better than the recursive algorithm given by David
Urlich.

Running the same code on the same machine using Unix Python compiled
for OS X, the above code is the fastest by a small but distinct margin.
What is more interesting, perhaps, is that the times were more than
twice as slow in the Unix version, expect for Emile's algorithm which
ran faster!

Moral: your mileage may vary.

Corran
(but list comprehensions are nice)

----
MacPython results:
range(15):
    bitshifting1 4.4
    bitshifting2 4.95
    recursive1 0.333333333333
    recursive2 0.283333333333
    comprehension1 0.283333333333
    comprehension2 0.266666666667
    bitshifting1 4.51666666667
    bitshifting2 4.68333333333
    recursive1 0.35
    recursive2 0.266666666667
    comprehension1 0.266666666667
    comprehension2 0.283333333333
range(18):
    recursive1 6.06666666667
    recursive2 2.3
    comprehension1 2.33333333333
    comprehension2 2.23333333333
    recursive1 2.83333333333
    recursive2 2.33333333333
    comprehension1 2.35
    comprehension2 2.21666666667

Unix Python results:
range(15):
    bitshifting1 3.56
    bitshifting2 7.09
    recursive1 0.69
    recursive2 0.65
    comprehension1 0.75
    comprehension2 0.54
    bitshifting1 3.74
    bitshifting2 6.87
    recursive1 0.69
    recursive2 0.72
    comprehension1 0.63
    comprehension2 0.54
range(18):
    recursive1 7.22
    recursive2 7.22
    comprehension1 7.96
    comprehension2 6.88
    recursive1 7.46
    recursive2 6.77
    comprehension1 7.73
    comprehension2 6.63

----
import time

# Emile van Sebille
def toggle(pattern):
    if pattern[-1] == 0:
        pattern[-1] = 1
    else:
        pattern[-1] = 0
        pattern[:-1] = toggle(pattern[:-1])
    return pattern

def genNibbles(qty):
    rslt = [[0]*qty]
    for i in xrange(2**qty - 1):
        rslt.append(toggle(rslt[-1][:]))
    return rslt

def bitshifting1(set):
    incl = genNibbles(len(set))
    sq = range(len(set))
    rslt = []
    for i in incl:
        sset = []
        for j in sq:
            if i[j] == 1:
                sset.append(set[j])
        rslt.append(sset)
    return rslt

# Alex Martelli
def bitshifting2(L):
    N = len(L)
    return [ [L[i] for i in range(N) if X&(1L<<i)]
        for X in range(2**N) ]

# Malcolm Tredinnick
def recursive1(seq):
        """
        To computer the powerset of seq, we need to know the powerset of
        seq[1:] and combine a copy of it with seq[0] (as well as keeping
        an unmodified copy).
        
        We stop the recursion when seq is a singleton -- the powerset of
        [a] is [[a], []].
        """
        # Trivial case
        if len(seq) == 0:
                return [[]]
        # Now do the recursion and combine the results
        subSet = recursive1(seq[1:])
        resultSoFar = subSet[:]
        for set in subSet:
                resultSoFar.append([seq[0]] + set)
        return resultSoFar

# David Urlich
def AddTo(list, elt):
        return list + [elt]

def recursive2(list):
  if list:
    ans = recursive2(list[:-1])
    return ans + map(AddTo, ans, [list[-1]]*len(ans))
  else:
    return [[]]

# Walter Vannini (slightly optimized)
def comprehension1( set ):
    return reduce (comprehension1aux, set, [ [] ])

def comprehension1aux( PowerSetSoFar, element):
    return PowerSetSoFar + [i+[element] for i in PowerSetSoFar ]

# Webster
def comprehension2(list):
        PowerSetSoFar = [[]]
        for element in list:
                PowerSetSoFar += [i+[element] for i in PowerSetSoFar ]
        return PowerSetSoFar

def timer(f, l):
        t1 = time.clock()
        f(l)
        t = time.clock() - t1
        print "   ", f.__name__, t
   

fns = (bitshifting1, bitshifting2, recursive1, recursive2,
comprehension1, comprehension2)
l =  range(15)

print "range(15):"
for f in fns:
    timer(f,l)
for f in fns:
    timer(f,l)

fns = recursive1, recursive2, comprehension1, comprehension2
l =  range(18)

print "range(18):"
for f in fns:
    timer(f,l)
for f in fns:
    timer(f,l)