大型迭代器的笛卡爾積（itertools）

Question

從previous question我學到了一些有趣的東西。如果Python的itertools.product被饋入一系列迭代器，則這些迭代器將在笛卡爾乘積開始之前在之前被轉換爲元組。 Relatedquestions查看itertools.product的源代碼得出的結論是，雖然沒有中間結果存儲在內存中，但在產品迭代開始之前創建了原始迭代器的元組版本。

問題：當（元組轉換）輸入太大而無法在內存中保存時，是否有辦法創建迭代器到笛卡爾乘積？簡單的例子：

import itertools 
A = itertools.permutations(xrange(100)) 
itertools.product(A) 

一個比較實用的情況下，會採取像原來實行的功能的一系列(*iterables[, repeat]) - 以上只是一個例子。它看起來並不像你可以使用當前的itertools.product實現，所以我歡迎用純Python提交（雖然你無法擊敗itertools的C後端！）。

Answer 1

這裏是它調用可調用和迭代iterables的實現，這是假設重新啓動：

def product(*iterables, **kwargs): 
    if len(iterables) == 0: 
     yield() 
    else: 
     iterables = iterables * kwargs.get('repeat', 1) 
     it = iterables[0] 
     for item in it() if callable(it) else iter(it): 
      for items in product(*iterables[1:]): 
       yield (item,) + items 

測試：

import itertools 
g = product(lambda: itertools.permutations(xrange(100)), 
      lambda: itertools.permutations(xrange(100))) 
print next(g) 
print sum(1 for _ in g) 

Answer 2

沒有「迭代器重新創建」，對於第一個因素可能是可能的。但那隻會節省1/n的空間（其中n是因子的數量）並增加混淆。

所以答案是迭代器重新創建。函數的客戶端必須確保迭代器的創建是純粹的（沒有副作用）。像

def iterProduct(ic): 
    if not ic: 
     yield [] 
     return 

    for i in ic[0](): 
     for js in iterProduct(ic[1:]): 
      yield [i] + js 


# Test 
x3 = lambda: xrange(3) 
for i in iterProduct([x3,x3,x3]): 
    print i 

Answer 3

這不能與標準Python生成器來完成，因爲一些迭代必須循環多次。你必須使用某種能夠「重複」的數據類型。我創建了一個簡單的「可重複」類和一個非遞歸產品算法。 product應該有更多的錯誤檢查，但這至少是第一種方法。簡單reiterable類...

class PermutationsReiterable(object): 
    def __init__(self, value): 
     self.value = value 
    def __iter__(self): 
     return itertools.permutations(xrange(self.value)) 

而且product iteslf ...

def product(*reiterables, **kwargs): 
    if not reiterables: 
     yield() 
     return 
    reiterables *= kwargs.get('repeat', 1) 

    iterables = [iter(ri) for ri in reiterables] 
    try: 
     states = [next(it) for it in iterables] 
    except StopIteration: 
     # outer product of zero-length iterable is empty 
     return 
    yield tuple(states) 

    current_index = max_index = len(iterables) - 1 
    while True: 
     try: 
      next_item = next(iterables[current_index]) 
     except StopIteration: 
      if current_index > 0: 
       new_iter = iter(reiterables[current_index]) 
       next_item = next(new_iter) 
       states[current_index] = next_item 
       iterables[current_index] = new_iter 
       current_index -= 1 
      else: 
       # last iterable has run out; terminate generator 
       return 
     else: 
      states[current_index] = next_item 
      current_index = max_index 
      yield tuple(states) 

測試：

>>> pi2 = PermutationsReiterable(2) 
>>> list(pi2); list(pi2) 
[(0, 1), (1, 0)] 
[(0, 1), (1, 0)] 
>>> list(product(pi2, repeat=2)) 
[((0, 1), (0, 1)), ((0, 1), (1, 0)), ((1, 0), (0, 1)), ((1, 0), (1, 0))] 
>>> giant_product = product(PermutationsReiterable(100), repeat=5) 
>>> len(list(itertools.islice(giant_product, 0, 5))) 
5 
>>> big_product = product(PermutationsReiterable(10), repeat=2) 
>>> list(itertools.islice(big_product, 0, 5)) 
[((0, 1, 2, 3, 4, 5, 6, 7, 8, 9), (0, 1, 2, 3, 4, 5, 6, 7, 8, 9)), 
((0, 1, 2, 3, 4, 5, 6, 7, 8, 9), (0, 1, 2, 3, 4, 5, 6, 7, 9, 8)), 
((0, 1, 2, 3, 4, 5, 6, 7, 8, 9), (0, 1, 2, 3, 4, 5, 6, 8, 7, 9)), 
((0, 1, 2, 3, 4, 5, 6, 7, 8, 9), (0, 1, 2, 3, 4, 5, 6, 8, 9, 7)), 
((0, 1, 2, 3, 4, 5, 6, 7, 8, 9), (0, 1, 2, 3, 4, 5, 6, 9, 7, 8))] 

Answer 4

對不起了這個話題，但花了幾個小時的調試後，一程序試圖迭代生成器的遞歸生成的笛卡爾乘積。我可以告訴你，如果不像上面所有例子那樣使用常數，那麼上述解決方案都不會起作用。

更正：

from itertools import tee 

def product(*iterables, **kwargs): 
    if len(iterables) == 0: 
     yield() 
    else: 
     iterables = iterables * kwargs.get('repeat', 1) 
     it = iterables[0] 
     for item in it() if callable(it) else iter(it): 
      iterables_tee = list(map(tee, iterables[1:])) 
      iterables[1:] = [it1 for it1, it2 in iterables_tee] 
      iterable_copy = [it2 for it1, it2 in iterables_tee] 
      for items in product(*iterable_copy): 
       yield (item,) + items 

如果您的發電機發電機包含，你需要一個拷貝傳遞給遞歸調用。