Powersets of a list?

Alex Martelli aleaxit at yahoo.com
Sun May 27 13:11:09 EDT 2001


"David C. Ullrich" <ullrich at math.okstate.edu> wrote in message
news:3b11015c.2099508 at nntp.sprynet.com...
    ...
> There have been several power set routines posted.
> I suspect that they're all O(N*2^N), but when I time
> them (on Windows, starting with a list of length 15)
> some of them are at least 10 time faster than others.

Yes, the multiplicative constants are indeed widely
different.

> I haven't had any reason to get 2.x so I haven't,
> on aint-broke grounds. So I can't compare what
> you wrote with, for example, the routine I posted.
> Have you compared them?

I had not measured performance, no -- just 'compared'
them in terms of compactness of source code.


> So although I don't see how what you posted
> works, I _do_ see how it works for lists

You're right, it didn't work (not even for lists
of length 4, since I had forgotten to compute N).

As an apology, here's the performance measurement
you requested.  First, the code -- all the versions of
powersets that were posted so far, with minimal
renaming (it seems there actually were no conflicts,
due to different usage of upper/lower case).

import time

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 powerset_Emile(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

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

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

def powerset_David(set):
    return PowerSet(list(set))

def powerSet(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) == 1:
        return [seq, []]
    # Now do the recursion and combine the results
    subSet = powerSet(seq[1:])
    resultSoFar = subSet[:]
    for set in subSet:
        resultSoFar.append([seq[0]] + set)
    return resultSoFar

def powerset_Malcolm(set):
    return powerSet(list(set))

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

class Powerset:
    def __init__(self, L):
        self.L = L
        self.N = len(L)
        self.S = 2**self.N
    def __getitem__(self, x):
        if x<0: x+=self.S
        if x<0 or x>=self.S: raise IndexError,x
        return [self.L[i] for i in range(self.N)
            if x&(1L<<i)]

def powerset_AlexClass(L):
    return Powerset(L)

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

def powerset_Walter( set ):
    return reduce (PowerSet2, set, [ [] ])

functs = [ (fn,fo) for fn, fo in globals().items()
    if callable(fo) and fn.startswith('powerset_') ]
functs.sort()

def timetest(seq, prn=None):
    base = None
    for fn, fo in functs:
        start=time.clock()
        rs = fo(seq)
        lrs = [x for x in rs]
        stend=time.clock()
        print "%s(%5.2f) %2d:"%(fn,stend-start,len(lrs)),
        lrs.sort()
        assert base is None or base == lrs
        base = lrs
        if prn:
            for x in lrs:
                print repr(''.join(x)),
        print

timetest('polye',1)
timetest('uzapolyekit')
timetest('xuzapolyekitjry')

and the output of one run:

D:\py21>python powset.py
powerset_Alex( 0.00) 32: '' 'e' 'l' 'le' 'ly' 'lye' 'o' 'oe' 'ol' 'ole'
'oly' 'o
lye' 'oy' 'oye' 'p' 'pe' 'pl' 'ple' 'ply' 'plye' 'po' 'poe' 'pol' 'pole'
'poly'
'polye' 'poy' 'poye' 'py' 'pye' 'y' 'ye'
powerset_AlexClass( 0.01) 32: '' 'e' 'l' 'le' 'ly' 'lye' 'o' 'oe' 'ol' 'ole'
'ol
y' 'olye' 'oy' 'oye' 'p' 'pe' 'pl' 'ple' 'ply' 'plye' 'po' 'poe' 'pol'
'pole' 'p
oly' 'polye' 'poy' 'poye' 'py' 'pye' 'y' 'ye'
powerset_David( 0.00) 32: '' 'e' 'l' 'le' 'ly' 'lye' 'o' 'oe' 'ol' 'ole'
'oly' '
olye' 'oy' 'oye' 'p' 'pe' 'pl' 'ple' 'ply' 'plye' 'po' 'poe' 'pol' 'pole'
'poly'
 'polye' 'poy' 'poye' 'py' 'pye' 'y' 'ye'
powerset_Emile( 0.00) 32: '' 'e' 'l' 'le' 'ly' 'lye' 'o' 'oe' 'ol' 'ole'
'oly' '
olye' 'oy' 'oye' 'p' 'pe' 'pl' 'ple' 'ply' 'plye' 'po' 'poe' 'pol' 'pole'
'poly'
 'polye' 'poy' 'poye' 'py' 'pye' 'y' 'ye'
powerset_Malcolm( 0.00) 32: '' 'e' 'l' 'le' 'ly' 'lye' 'o' 'oe' 'ol' 'ole'
'oly'
 'olye' 'oy' 'oye' 'p' 'pe' 'pl' 'ple' 'ply' 'plye' 'po' 'poe' 'pol' 'pole'
'pol
y' 'polye' 'poy' 'poye' 'py' 'pye' 'y' 'ye'
powerset_Walter( 0.00) 32: '' 'e' 'l' 'le' 'ly' 'lye' 'o' 'oe' 'ol' 'ole'
'oly'
'olye' 'oy' 'oye' 'p' 'pe' 'pl' 'ple' 'ply' 'plye' 'po' 'poe' 'pol' 'pole'
'poly
' 'polye' 'poy' 'poye' 'py' 'pye' 'y' 'ye'
powerset_Alex( 0.75) 2048:
powerset_AlexClass( 0.63) 2048:
powerset_David( 0.06) 2048:
powerset_Emile( 0.37) 2048:
powerset_Malcolm( 0.08) 2048:
powerset_Walter( 0.14) 2048:
powerset_Alex(11.48) 32768:
powerset_AlexClass(12.94) 32768:
powerset_David( 2.00) 32768:
powerset_Emile( 7.37) 32768:
powerset_Malcolm( 2.49) 32768:
powerset_Walter( 3.49) 32768:

As a side effect, this does show the same powersets, net of order,
are being returned.


Alex







More information about the Python-list mailing list