迭代itertools.product以不同的顺序没有创建列表

Question

我有一个可迭代的涵盖了一个巨大的搜索空间。我的计划是不让脚本终止，而是在一段时间后杀死脚本。

现在我需要这个空间的笛卡尔积，并在那里搜索。 itertools.product产生顺序如下：

>>> list(itertools.product(range(3), repeat=2)) 
[(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2, 1), (2, 2)] 

当我想以一种类似于对角线为了寻找：

[(0, 0), (0, 1), (1, 0), (0, 2), (1, 1), (2, 0), (1, 2), (2, 1), (2, 2)] 

sorted与一些关键的函数，返回数组的元素的总和将是我的规则方法，但是需要检查所有需要检查的数据，这在我的情况下是不可行的。有没有办法做到这一点？

此问题与this one非常相似，但仍有sorted仍在使用中。另外我不会很快看到如何将ordered_combinations改编为ordered_product。

Answer 1

问题等同于问如何创建所有n元组与给定的总和连续和增加值的总和：

    (0, 0),    sum == 0 
       (0, 1), (1, 0),   sum == 1 
     (0, 2), (1, 1), (2, 0),   sum == 2 
      (1, 2), (2, 1),   sum == 3 
        (2, 2)    sum == 4 

对于任何给定的行（与给定的目标总）子问题相当于动态规划问题Number of ways to make change for amount N或Number of ways to add up to a sum S with N numbers。

另请参阅Donald Knuth编写的Combinatorial Algorithms。

Answer 2

它实际上很容易计算的对角线指数为repeat=2情况：

def diagonal_product(inp): 
    inp = tuple(inp) 
    n = len(inp) 
    # upper left triangle 
    for i in range(n): 
     for j in range(i+1): 
      yield inp[i-j], inp[j] 
    # lower right triangle 
    for i in range(1, n): 
     for j in range(n-i): 
      yield inp[n-j-1], inp[i+j] 

只是为了显示结果：

>>> list(diagonal_product(range(4))) 
[(0, 0), (1, 0), (0, 1), (2, 0), (1, 1), (0, 2), (3, 0), (2, 1), (1, 2), 
(0, 3), (3, 1), (2, 2), (1, 3), (3, 2), (2, 3), (3, 3)] 

>>> list(diagonal_product(range(3))) 
[(0, 0), (1, 0), (0, 1), (2, 0), (1, 1), (0, 2), (2, 1), (1, 2), (2, 2)] 

函数本身可能会更复杂一些（或更慢）比它需要，但我还没有找到任何参考实现这种情况下。

在range输入你也可以避免所有的索引和的情况下，只返回指数：

def diagonal_product(n): 
    # upper left triangle 
    for i in range(n): 
     for j in range(i+1): 
      yield i-j, j 
    # lower right triangle 
    for i in range(1, n): 
     for j in range(n-i): 
      yield n-j-1, i+j 

list(diagonal_product(3)) 
# [(0, 0), (1, 0), (0, 1), (2, 0), (1, 1), (0, 2), (2, 1), (1, 2), (2, 2)]