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