我正在寻找一种生成整数固定长度分区的所有排列的算法。顺序无所谓。
例如，对于 n=4 和长度 L=3：
[(0, 2, 2), (2, 0, 2), (2, 2, 0),
(2, 1, 1), (1, 2, 1), (1, 1, 2),
(0, 1, 3), (0, 3, 1), (3, 0, 1), (3, 1, 0), (1, 3, 0), (1, 0, 3),
(0, 0, 4), (4, 0, 0), (0, 4, 0)]
我对整数分区 + 长度小于 L 的分区的排列感到困惑；但这太慢了，因为我多次获得相同的分区（因为[0, 0, 1]可能是[0, 0, 1];-)
任何帮助表示赞赏，不，这不是家庭作业——个人兴趣:-)
正如@pbarranis 所指出的，@rlibby 的代码在n等于k时不包括所有列表。下面是包含所有列表的 Python 代码。此代码是非递归的，这在内存使用方面可能更有效。
def successor(n, l):
idx = [j for j in range(len(l)) if l[j] < l[0]-1]
if not idx:
return False
i = idx[0]
l[1:i+1] = [l[i]+1]*(len(l[1:i+1]))
l[0] = n - sum(l[1:])
return True
def partitions(n, k):
l = [0]*k
l[0] = n
results = []
results.append(list(l))
while successor(n, l):
results.append(list(l))
return results
列表是按字典顺序创建的（算法和更多描述在这里）。
好的。首先，忘记排列，只生成长度为 L 的分区（如@Svein Bringsli 所建议的那样）。请注意，对于每个分区，您可以对元素进行排序，例如 >。现在只需“计数”即可维持您的订单。对于 n = 4，k = 3：
(4, 0, 0)
(3, 1, 0)
(2, 2, 0)
(2, 1, 1)
那么，如何实现呢？它看起来像：从位置 i 减去 1 并将其添加到下一个位置保持我们的顺序，从位置 i 减去 1，在位置 i + 1 上加 1，然后移动到下一个位置。如果我们处于最后一个位置，请退后一步。
这是一个小python，它就是这样做的：
def partition_helper(l, i, result):
if i == len(l) - 1:
return
while l[i] - 1 >= l[i + 1] + 1:
l[i] -= 1
l[i + 1] += 1
result.append(list(l))
partition_helper(l, i + 1, result)
def partition(n, k):
l = [n] + [0] * (k - 1)
result = [list(l)]
partition_helper(l, 0, result)
return result
现在您有一个列表列表（实际上是一个多集列表），并且生成列表的每个多集的所有排列可以为您提供解决方案。我不会深入讨论，有一个递归算法，它基本上说，对于每个位置，选择多重集中的每个唯一元素，并附加从多重集中删除该元素所产生的多重集的排列。
我发现使用递归函数对于更大的长度和整数并不好，因为它会消耗太多的 RAM，并且使用生成器/可恢复函数（即“产生”值）太慢并且需要一个大型库来使其交叉-平台。
所以这里有一个 C++ 中的非递归解决方案，它按排序顺序生成分区（这也是排列的理想选择）。我发现这比我为 4 或更大的分区长度尝试的看似聪明和简洁的递归解决方案快 10 倍以上，但对于 1-3 的长度，性能不一定更好（而且我不关心短长度，因为它们对任何一种方法都很快）。
// Inputs
unsigned short myInt = 10;
unsigned short len = 3;
// Partition variables.
vector<unsigned short> partition(len);
unsigned short last = len - 1;
unsigned short penult = last - 1;
short cur = penult; // Can dip into negative value when len is 1 or 2. Can be changed to unsigned if len is always >=3.
unsigned short sum = 0;
// Prefill partition with 0.
fill(partition.begin(), partition.end(), 0);
do {
// Calculate remainder.
partition[last] = max(0, myInt - sum); // Would only need "myInt - sum" if partition vector contains signed ints.
/*
*
* DO SOMETHING WITH "partition" HERE.
*
*/
if (partition[cur + 1] <= partition[cur] + 1) {
do {
cur--;
} while (
cur > 0 &&
accumulate(partition.cbegin(), partition.cbegin() + cur, 0) + (len - cur) * (partition[cur] + 1) > myInt
);
// Escape if seeked behind too far.
// I think this if-statement is only useful when len is 1 or 2, can probably be removed if len is always >=3.
if (cur < 0) {
break;
}
// Increment the new cur position.
sum++;
partition[cur]++;
// The value in each position must be at least as large as the
// value in the previous position.
for (unsigned short i = cur + 1; i < last; ++i) {
sum = sum - partition[i] + partition[i - 1];
partition[i] = partition[i - 1];
}
// Reset cur for next time.
cur = penult;
}
else {
sum++;
partition[penult]++;
}
} while (myInt - sum >= partition[penult]);
我在这里写了用“分区”做一些事情的地方。是您实际消耗价值的地方。（在最后一次迭代中，代码将继续执行循环的其余部分，但我发现这比不断检查退出条件要好——它针对更大的操作进行了优化）
0,0,10 0,1,9 0,2,8 0,3,7 0,4,6 0,5,5 1,1,8 1,2,7 1,3,6 1,4,5 2,2,6 2,3,5 2,4,4 3,3,4
哦，我使用了“无符号短”，因为我知道我的长度和整数不会超过某些限制，如果它不适合你，请更改它:) 检查评论；必须对那里的一个变量（cur）进行签名以处理 1 或 2 的长度，并且有一个相应的 if 语句与之相伴，我还在评论中指出，如果您的分区向量已签名整数，则还有另一行可以简化。
为了得到所有的组合，在 C++ 中我会使用这个简单的排列策略，幸运的是它不会产生任何重复：
do {
// Your code goes here.
} while (next_permutation(partition.begin(), partition.end()));
将它嵌套在DO SOMETHING WITH “partition” HERE点中，你就可以开始了。
查找组合的替代方法（基于此处的 Java 代码https://www.nayuki.io/page/next-lexicographical-permutation-algorithm）如下。我发现这比 next_permutation() 执行得更好。
// Process lexicographic permutations of partition (compositions).
composition = partition;
do {
// Your code goes here.
// Find longest non-increasing suffix
i = last;
while (i > 0 && composition[i - 1] >= composition[i]) {
--i;
}
// Now i is the head index of the suffix
// Are we at the last permutation already?
if (i <= 0) {
break;
}
// Let array[i - 1] be the pivot
// Find rightmost element that exceeds the pivot
j = last;
while (composition[j] <= composition[i - 1])
--j;
// Now the value array[j] will become the new pivot
// Assertion: j >= i
// Swap the pivot with j
temp = composition[i - 1];
composition[i - 1] = composition[j];
composition[j] = temp;
// Reverse the suffix
j = last;
while (i < j) {
temp = composition[i];
composition[i] = composition[j];
composition[j] = temp;
++i;
--j;
}
} while (true);
您会注意到那里有一些未声明的变量，只需在代码中的所有 do-loop 之前声明它们：i、j、pos和temp（无符号短裤）和composition（与 相同的类型和长度partition）。您可以i在分区代码片段的 for 循环中重用 for 的声明。还要注意像正在使用的变量last，它假定此代码嵌套在前面给出的分区代码中。
同样，“您的代码在此处”是您出于自己的目的使用该组合物的地方。
供参考这里是我的标题。
#include <vector> // for std::vector
#include <numeric> // for std::accumulate
#include <algorithm> // for std::next_permutation and std::max
using namespace std;
尽管使用这些方法大大提高了速度，但对于任何相当大的整数和分区长度，这仍然会让你对你的 CPU 生气:)
就像我上面提到的，我无法让@rlibby 的代码满足我的需要，我需要 n=l 的代码，所以只是你需要的一个子集。下面是我的 C# 代码。我知道这不是上述问题的完美答案，但我相信您只需要修改第一种方法即可使其适用于不同的 l 值；基本上添加了与@rlibby 相同的代码，使数组长度为 l 而不是长度为 n。
public static List<int[]> GetPartitionPermutations(int n)
{
int[] l = new int[n];
var results = new List<int[]>();
GeneratePermutations(l, n, n, 0, results);
return results;
}
private static void GeneratePermutations(int[] l, int n, int nMax, int i, List<int[]> results)
{
if (n == 0)
{
for (; i < l.Length; ++i)
{
l[i] = 0;
}
results.Add(l.ToArray());
return;
}
for (int cnt = Math.Min(nMax, n); cnt > 0; --cnt)
{
l[i] = cnt;
GeneratePermutations(l, (n - cnt), cnt, i + 1, results);
}
}
大量搜索导致了这个问题。这是一个包含排列的答案：
#!/usr/bin/python
from itertools import combinations_with_replacement as cr
def all_partitions(n, k):
"""
Return all possible combinations that add up to n
i.e. divide n objects in k DISTINCT boxes in all possible ways
"""
all_part = []
for div in cr(range(n+1), k-1):
counts = [div[0]]
for i in range(1, k-1):
counts.append(div[i] - div[i-1])
counts.append(n-div[-1])
all_part.append(counts)
return all_part
例如，OP 要求的 all_part(4, 3) 给出：
[[0, 0, 4],
[0, 1, 3],
[0, 2, 2],
[0, 3, 1],
[0, 4, 0],
[1, 0, 3],
[1, 1, 2],
[1, 2, 1],
[1, 3, 0],
[2, 0, 2],
[2, 1, 1],
[2, 2, 0],
[3, 0, 1],
[3, 1, 0],
[4, 0, 0]]