我有一个数组，其长度为 X 。数组中的每个元素都有一系列 1 ..→。我想通过所有排列组合，有一笔有效地遍历→。

I have an array and its length is X. Each element of the array has range 1 .. L. I want to iterate efficiently through all array combinations that has sum L.

有正确的解决方案：L = 4，X = 2

Correct solutions for: L = 4 and X = 2

1 3
3 1
2 2

有正确的解决方案：L = 5，X = 3

Correct solutions for: L = 5 and X = 3

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

天真的实现（怪不得）我的问题太慢（X达在我的情况和L 8是多达128个）。

The naive implementation is (no wonder) too slow for my problem (X is up to 8 in my case and L is up to 128).

有谁告诉我怎么叫或在这个问题找到一个快速算法问题？

Could anybody tell me how is this problem called or where to find a fast algorithm for the problem?

谢谢！

推荐答案

如果我理解正确的话，你在给定的两个数字1≤ X 的≤→的，你想生成长度正整数的 X 的那笔的→的

If I understand correctly, you're given two numbers 1 ≤ X ≤ L and you want to generate all sequences of positive integers of length X that sum to L.

（注：这是类似于整数划分问题，但不相同的，因为你认为1,2,2是一个不同的序列从2,1,2，而在整数分区的问题我们忽略的顺序，从而使这些被认为是相同的分区。）

(Note: this is similar to the integer partition problem, but not the same, because you consider 1,2,2 to be a different sequence from 2,1,2, whereas in the integer partition problem we ignore the order, so that these are considered to be the same partition.)

这是你正在寻找对应于组合的 X - 1件出的→的 - 1。因为，如果我们把数字1到的→的 - 1的顺序，并挑选的 X 的 - 1人，那么所选择的数字之间间隔的长度为正整数的总和的→的

The sequences that you are looking for correspond to the combinations of X − 1 items out of L − 1. For, if we put the numbers 1 to L − 1 in order, and pick X − 1 of them, then the lengths of intervals between the chosen numbers are positive integers that sum to L.

例如，假设的→的是16的 X 的是5。然后，从1到15包容性选择4个号码：

For example, suppose that L is 16 and X is 5. Then choose 4 numbers from 1 to 15 inclusive:

...添加0在在端开始和16以及间隔是：

Add 0 at the beginning and 16 at the end, and the intervals are:

和3 + 4 + 1 + 6 + 2 = 16的要求。

and 3 + 4 + 1 + 6 + 2 = 16 as required.

所以产生的 X 的的组合 - 1件出的→的 - 1，并为每一个，将其转换为一个分区通过找到时间间隔。例如，在Python中，你可以这样写：

So generate the combinations of X − 1 items out of L − 1, and for each one, convert it to a partition by finding the intervals. For example, in Python you could write:

from itertools import combinations

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

>>> 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)]

有（→的 - 1）！ /（ X 的 - 1）（→的 - 的 X 的）！组合的 X 的 - 1件出的→的 - 1，所以这种算法（以及其输出的大小）的运行时间是指数中的→。但是，如果不计的输出，只需要O（→的）空间。

There are (L − 1)! / (X − 1)!(L − X)! combinations of X − 1 items out of L − 1, so the runtime of this algorithm (and the size of its output) is exponential in L. However, if you don't count the output, it only needs O(L) space.

使用的→的= 128和 X 的= 8，有89356415775分区，所以它会需要一段时间才能输出他们！

With L = 128 and X = 8, there are 89,356,415,775 partitions, so it'll take a while to output them all!

（也许如果您解释一下为什么要计算这些分区，我们也许能够提出符合您的要求，而无需实际生产它们的某种方式。）

(Maybe if you explain why you are computing these partitions, we might be able to suggest some way of meeting your requirements without having to actually produce them all.)