Powersets of a list?

[Emile van Sebille]

"David C. Ullrich" <ullrich at math.okstate.edu> wrote in message
news:3b11015c.2099508 at nntp.sprynet.com...
> On Sat, 26 May 2001 20:09:20 +0200, "Alex Martelli"
<snip>
> 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.
>

Timing results for four of the powerset generators posted to this thread
(format edited for usenet):

SetSize: 5   enum recurs1 recurs2 lComp
 reps:  5 :  0.01   0.00    0.00   0.02
 reps: 10 :  0.02   0.00    0.01   0.02
 reps: 15 :  0.03   0.01    0.01   0.04
SetSize: 10
 reps:  5 :  0.50   0.08    0.06   0.63
 reps: 10 :  1.01   0.14    0.13   1.24
 reps: 15 :  1.46   0.23    0.19   1.88
SetSize: 15
 reps:  5 : 26.23   6.75    5.84  32.00
 reps: 10 : 56.81  13.31   14.05  64.70
 reps: 15 : 90.25  20.51   25.01  97.16

--

Emile van Sebille
emile at fenx.com

---------

#---powersetTimings.py

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 enum(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 recurs1(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 = recurs1(seq[1:])
    resultSoFar = subSet[:]
    for set in subSet:
        resultSoFar.append([seq[0]] + set)
    return resultSoFar


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

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


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



from time import time

for setSize in (3, 8, 15):
    print "\n\nSetSize: %s" % setSize
    set = range(setSize)
    for iterations in (5, 10, 25):
        print ("\n\n%6d : " % iterations),
        for func in (enum, recurs1, recurs2, lComp):
            print '%8s:' % func.__name__,
            start = time()
            for i in range(iterations):
                assert len(func(set)) == 2**setSize
            print '%5.2f' % (time()-start),