cách mã một chức năng tương tự như itertools.product trong python 2.5

Question

Tôi có một danh sách các hàng, ví dụ:

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

và muốn tạo ra tất cả các hoán vị với một mục từ mỗi tuple.

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

Tôi có thể có bất kỳ số lượng bộ và bộ nào có thể có bất kỳ số phần tử nào. Và tôi không thể sử dụng itertools.product() vì python 2.5.

Answer 1

docs của itertools.product có một ví dụ về làm thế nào để thực hiện nó trong 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

Các tài liệu itertools chứa mã đầy đủ cho thấy những gì mỗi chức năng tương đương với. Việc triển khai product là 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

Khi chơi xung quanh với máy phát điện, tôi cũng tìm thấy một phiên bản của itertools.product, và nó gần như là nhanh như (bản địa) phiên bản thư viện, trong khi được 100% tương thích với nó, và nó không xây dựng kết quả trung gian :

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 

Với python 2.7.3, tôi thấy hiệu suất thực sự tốt (thường chỉ chậm hơn khoảng 5-10 lần với mức sử dụng bộ nhớ).

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