python - 在不创建列表的情况下以不同的顺序迭代 itertools.product

Question

我有一个覆盖巨大搜索空间的iterable。我的计划不是让脚本终止，而是在一定时间后将其终止。

现在我需要这个空间的笛卡尔积并在那里搜索。 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 .

另请参阅 Combinatorial Algorithms 中的评论唐纳德·高德纳 (Donald Knuth)。