python - 如何迭代笛卡尔积以便首先组合顶级项目？

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')]

相反，我希望在 (1, 'c') 之前看到 (2, 'a')。确切的顺序，例如(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])