cómo el código de una función similar a itertools.product en Python 2.5

Question

Tengo una lista de tuplas, por ejemplo:

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

y quiero generar todas las permutaciones con un artículo de cada tupla.

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

Puedo tener cualquier cantidad de tuplas y una tupla puede tener cualquier cantidad de elementos. Y no puedo usar itertools.product() porque Python 2.5.

Answer 1

documentos de itertools.product tienen un ejemplo de cómo implementarlo en 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

La documentación itertools contiene el código completo que muestra lo que cada función es equivalente a. La implementación product es here.

Answer 3

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 4

Al jugar con los generadores, yo también encontré una versión de itertools.product, y es casi tan rápido como el (nativo) versión de la biblioteca, mientras que ser 100% compatible con él, y no se acumula resultados intermedios :

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 

con Python 2.7.3, encontré el rendimiento sea muy bueno (por lo general sólo alrededor de un factor de 5-10 lento con esencialmente el mismo uso de la memoria).

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