我发现使用递归函数对于更大的长度和整数并不好,因为它会消耗太多的 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 生气:)