以不同顺序迭代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使用一些返回元组元素总和的关键函数将是我的常规方法,但是对于排序所有数据都需要检查,这在我的情况下是不可行的.有没有办法做到这一点？

这个问题很相似,这一个,但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 ofways to make change for amount N或Number ofways to add a sum S with N 个数字。

另请参阅 Donald Knuth 撰写的《组合算法》中的文章。