Creating unique combinations from lists

[Reedick, Andrew]

> -----Original Message-----
> From: python-list-bounces+jr9445=att.com at python.org [mailto:python-
> list-bounces+jr9445=att.com at python.org] On Behalf Of Tim Chase
> Sent: Wednesday, January 16, 2008 3:40 PM
> To: breal
> Cc: python-list at python.org
> Subject: Re: Creating unique combinations from lists
> 
> You can use a recursive generator:
> 
>    def iterall(*iterables):
>      if iterables:
>        for head in iterables[0]:
>          for remainder in iterall(*iterables[1:]):
>            yield [head] + remainder
>      else:
>        yield []
> 
>    for thing in iterall(
>        ['big', 'medium', 'small'],
>        ['old', 'new'],
>        ['blue', 'green'],
>        ):
>      print thing
 

Recursion definitely makes for an elegant solution.  However you do take
a bit of a performance hit.  If performance matters (and comprehensions
are supposed to be optimized/fast) and you want a "works for N nested
loops solution," then you could build a N deep comprehension on the fly
and eval() it:


def gen(lists):
	out =  '[' + ','.join(["v%s" % i for i in range(len(lists))]) +
']'
	comp = ''.join([ " for v%d in lists[%d]" % (i, i) for i in
range(len(lists))])
	return eval('[ ' + out + comp + ' ]')

gen([a, b, c])


So for a three item list, it would build and execute the following
comprehension:
	[ [v0,v1,v2] for v0 in lists[0] for v1 in lists[1] for v2 in
lists[2] ]
Seven item list:
	[ [v0,v1,v2,v3,v4,v5,v6] for v0 in lists[0] for v1 in lists[1]
for v2 in lists[2] for v3 in lists[3] for v4 in lists[4] for v5 in
lists[5] for v6 in lists[6] ]


Some rough performance numbers in seconds for 1,000 iterations over a
three item list:
	list comprehension:  0.74
	nested for loop   :  0.97  31% slower
	recursion         :  3.91 428% slower  =P
	eval              :  1.11  50% slower





from timeit import Timer

s = "a = [ i for i in range(10) ]; b = a; c = a"

t = Timer( "l = [ [i, j, k] for i in a for j in b for k in c]", s)

iterations = 1000

print "list comprehension:  %4.2f" % t.timeit(iterations)


t = Timer('''
l = [] 
for i in a:
    for j in b: 
        for k in c:
            l.append([i, j, k])
''', s)

print "nested for loop   :  %4.2f" % t.timeit(iterations)


t = Timer('''
    def iterall(*iterables):
        if iterables:
            for head in iterables[0]:
                for remainder in iterall(*iterables[1:]):
                    yield [head] + remainder
        else:
            yield []

    for thing in iterall(a, b, c):
        pass #print thing
        ''', s)

print "recursion         :  %4.2f" % t.timeit(iterations)


t = Timer('''
    def gen(lists):
        out =  '[' + ','.join(["v%s" % i for i in range(len(lists))]) +
']'
        comp = ''.join([ " for v%d in lists[%d]" % (i, i) for i in
range(len(lists))])
        return eval('[ ' + out + comp + ' ]')
    gen([a, b, c])
''', s)

print "eval              :  %4.2f" % t.timeit(iterations)



*****

The information transmitted is intended only for the person or entity to which it is addressed and may contain confidential, proprietary, and/or privileged material. Any review, retransmission, dissemination or other use of, or taking of any action in reliance upon this information by persons or entities other than the intended recipient is prohibited. If you received this in error, please contact the sender and delete the material from all computers. GA621