How code function is similar to itertools.product in python 2.5

Question

I have a list of tuples, for example:

A=[(1,2,3), (3,5,7,9), (7)] 

and you want to generate all permutations with one element from each tuple.

 1,3,7 1,5,7 1,7,7 ... 3,9,7 

I can have any number of tuples, and a tuple can have any number of elements. And I can not use itertools.product() , because python 2.5.

Answer 1

docs itertools.product is an example of how to implement it in py2.5:

 def product(*args, **kwds): # product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy # product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111 pools = map(tuple, args) * kwds.get('repeat', 1) result = [[]] for pool in pools: result = [x+[y] for x in result for y in pool] for prod in result: yield tuple(prod) 

Answer 2

 def product(*iterables): """ Equivalent of itertools.product for versions < 2.6, which does NOT build intermediate results. Omitted 'repeat' option. product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy """ nIters = len(iterables) lstLenths = [] lstRemaining = [1] for i in xrange(nIters-1,-1,-1): m = len(iterables[i]) lstLenths.insert(0, m) lstRemaining.insert(0, m * lstRemaining[0]) nProducts = lstRemaining.pop(0) for p in xrange(nProducts): lstVals = [] for i in xrange(nIters): j = p/lstRemaining[i]%lstLenths[i] lstVals.append(iterables[i][j]) yield tuple(lstVals) 

Answer 3

The itertools documentation contains complete code showing that each function is equivalent. The product implementation is here .

Answer 4

When playing with generators, I also found the version of itertools.product , and it is almost as fast as the version of the (native) library, and is 100% compatible with it, and it does not produce intermediate results:

 def product(*args, **kwds): "Alternative fast implementation of product for python < 2.6" def cycle(sequence, uplevel): while True: vals = next(uplevel) # advance upper level, raises if done it = iter(sequence) # (re-)start iteration of current level try: while True: yield vals + (next(it),) except StopIteration: pass step = iter(((),)) for pool in map(tuple, args)*kwds.get('repeat', 1): step = cycle(pool, step) # build stack of iterators return step 

With python 2.7.3, I found that the performance is really good (usually only about 5-10 slower, essentially with the same memory usage).

 >>> import itertools as itt >>> timeit for _ in itt.product(range(20), range(3), range(150)): pass 1000 loops, best of 3: 221 µs per loop >>> timeit for _ in product(range(20), range(3), range(150)): pass 1000 loops, best of 3: 1.14 ms per loop