come il codice di una funzione simile a itertools.product in Python 2.5

Question

ho una lista di tuple, per esempio:

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

e voglio generare tutte le permutazioni con un elemento di ogni tupla.

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

Posso avere un numero qualsiasi di tuple e una tupla può avere un numero qualsiasi di elementi. E non posso usare itertools.product() perché python 2.5.

Answer 1

documenti di itertools.product hanno un esempio di come implementare 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

La documentazione itertools contiene codice completo mostrando ciò ogni funzione è equivalente a. L'implementazione product è 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

Quando si gioca in giro con i generatori, ho anche trovato una versione di itertools.product, ed è quasi veloce come il (nativo) versione della libreria, pur essendo compatibile al 100% con esso, e non costruisce risultati intermedi :

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, ho trovato le prestazioni per essere veramente buono (di solito solo circa un fattore di 5-10 lento con essenzialmente lo stesso utilizzo della 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