algorithm - 如何有效地迭代具有常量和的数组组合？

Question

我有一个数组，它的长度是X。数组的每个元素的范围都是 1 .. L。我想高效地遍历所有具有总和 L 的数组组合。

正确的解决方案:L = 4 和 X = 2

1 3
3 1
2 2

正确的解决方案:L = 5 和 X = 3

1 1 3
1 3 1
3 1 1
1 2 2
2 1 2
2 2 1

天真的实现(难怪)对于我的问题来说太慢了(在我的例子中 X 最大为 8，L 最大为 128)。

谁能告诉我这个问题是怎么命名的，或者在哪里可以找到解决该问题的快速算法？

谢谢!

Answer 1

如果我没理解错的话，给你两个数字 1 ≤ X ≤ L 并且你想生成所有长度为 X< 的正整数序列/em> 总和为 L。

(注意:这类似于 integer partition problem ，但不相同，因为您认为 1,2,2 与 2,1,2 是不同的序列，而在整数分区问题中我们忽略顺序, 所以这些被认为是同一个分区。)

您要查找的序列对应于 combinations X - 1 个项目，从 L - 1 中。因为，如果我们将数字 1 到 L - 1 按顺序排列，然后选择 < em>X − 1 个，则所选数字之间的间隔长度为正整数，总和为 L。

例如，假设L为16，X为5，则从1到15中选出4个数:

开头加0，结尾加16，区间为:

和 3 + 4 + 1 + 6 + 2 = 16 根据需要。

所以 generate the combinations X − 1 个项目，共 L - 1 个，对于每个项目，通过查找间隔将其转换为一个分区。例如，在 Python 中你可以这样写:

from itertools import combinations

def partitions(n, t):
    """
    Generate the sequences of `n` positive integers that sum to `t`.
    """
    assert(1 <= n <= t)
    def intervals(c):
        last = 0
        for i in c:
            yield i - last
            last = i
        yield t - last
    for c in combinations(range(1, t), n - 1):
        yield tuple(intervals(c))

>>> list(partitions(2, 4))
[(1, 3), (2, 2), (3, 1)]
>>> list(partitions(3, 5))
[(1, 1, 3), (1, 2, 2), (1, 3, 1), (2, 1, 2), (2, 2, 1), (3, 1, 1)]

有(L - 1)!/(X − 1)!(L − X)! X − 1 个项目与 L − 1 的组合，因此该算法的运行时间(及其输出的大小)在 L。但是，如果不计算输出，它只需要O(L)空间。

L = 128，X = 8，有 89,356,415,775 个分区，所以需要一段时间才能全部输出!

(也许如果您解释为什么要计算这些分区，我们可能会建议一些方法来满足您的要求，而不必实际生成它们。)