如何迭代笛卡爾產品，以便首先結合頂級項目？

Question

我需要得到迭代的笛卡爾積，如itertools.product給我，但爲了優化的原因，我希望那些索引總數最低的對/組合首先出現。

因此，舉例來說，如果我有兩個列表，a = [1, 2, 3, 4, 5]和b = ['a', 'b', 'c', 'd', 'e']，itertools.product給我：

>>> list(itertools.product(a, b)) 
[(1, 'a'), (1, 'b'), (1, 'c'), (1, 'd'), (1, 'e'), (2, 'a'), (2, 'b'), (2, 'c'), (2, 'd'), (2, 'e'), (3, 'a'), (3, 'b'), (3, 'c'), (3, 'd'), (3, 'e'), (4, 'a'), (4, 'b'), (4, 'c'), (4, 'd'), (4, 'e'), (5, 'a'), (5, 'b'), (5, 'c'), (5, 'd'), (5, 'e')] 

相反，我希望看到(2, 'a')(1, 'c')之前。確切的順序，例如(1, 'b')和(2, 'a')，是不重要的。

---

目前，我正在整理基於指數的產品範圍的列表：

>>> sorted(list(itertools.product(range(len(a)), range(len(b)))), lambda a, b: sum(a) - sum(b)) 
[(0, 0), (0, 1), (1, 0), (0, 2), (1, 1), (2, 0), (0, 3), (1, 2), (2, 1), (3, 0), (0, 4), (1, 3), (2, 2), (3, 1), (4, 0), (1, 4), (2, 3), (3, 2), (4, 1), (2, 4), (3, 3), (4, 2), (3, 4), (4, 3), (4, 4)] 

然後使用該索引列表。但是，這會佔用太多的長列表的內存。我需要一種與itertools.product具有相同調用約定的生成器，但是我無法弄清楚迭代的方式，因此我只需將一次訂購和所有可能的訂單都完成一次。

Answer 1

def cartprod(x,y): 
    nx = len(x) 
    ny = len(y) 
    for i in range(nx+ny): 
     for j in range(max(0,i-ny+1), min(i+1,nx)): 
      yield (x[j],y[i-j]) 

Answer 2

更新以下@otus評論 - 由總和排序生成指數，用這些來查找值：

A = range(5) 
B = 'abcde' 

def indices(A,B): 
    # iterate all possible target sums in order 
    for m in range(max(A)+max(B)): 
     for a in A: 
      # stop once current target sum isn't possible 
      if a > m: 
       break 
      # yield if sum equals current target sum 
      if m-a in B: 
       yield a,m-a 

def values(A,B): 
    for a,b in indices(range(len(A)),set(range(len(B)))): 
     yield A[a],B[b] 

print list(values(A,B)) 

輸出：

[(0, 'a'), (0, 'b'), (1, 'a'), (0, 'c'), (1, 'b'), (2, 'a'), (0, 'd'), (1, 'c'), (2, 'b'), (3, 'a'), (0, 'e'), (1, 'd'), (2, 'c'), (3, 'b'), (4, 'a'), (1, 'e'), (2, 'd'), (3, 'c'), (4, 'b'), (2, 'e'), (3, 'd'), (4, 'c'), (3, 'e'), (4, 'd')]