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

Question

我有一个数组，它的长度是X. 数组的每个元素都有 range 1 .. L。我想有效地遍历所有具有 sum 的数组组合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且总和为L的正整数序列。

（注意：这类似于整数分区问题，但不一样，因为您认为 1,2,2 与 2,1,2 是不同的序列，而在整数分区问题中我们忽略了顺序，因此这些被认为是同一个分区。）

您正在寻找的序列对应于L - 1中X  - 1 个项目的组合 。因为，如果我们将数字 1 到L  - 1 按顺序排列，并从中选择X  - 1 个，则区间的长度所选数字之间是总和为L的正整数。

例如，假设L为 16，X为 5。然后从 1 到 15（含）中选择 4 个数字：

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

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

因此，从L -1 中生成X  -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  − <em>X)! L - 1 中X  - 1 个项目的组合 ，因此该算法的运行时间（及其输出的大小）在L中是指数的。但是，如果不计算输出，它只需要 O( L ) 空间。

在L  = 128 和X  = 8 的情况下，有 89,356,415,775 个分区，因此需要一段时间才能将它们全部输出！

（也许如果您解释为什么要计算这些分区，我们可能会提出一些满足您要求的方法，而不必实际生成所有分区。）