c++ - 三重限制正整数组合的非递归枚举
问题描述
在创建了一个迭代（非递归）函数之后，该函数以字典顺序枚举正整数的双重限制组合，对于具有非常少量 RAM（但大 EPROM）的微控制器，我不得不将限制数量扩展到 3 ，即：
- 对作品长度的限制
- 元素最小值的限制
- 元素最大值的限制
下面列出了生成双重限制组合的原始函数：
void GenCompositions(unsigned int myInt, unsigned int CompositionLen, unsigned int MinVal)
{
if ((MinVal = MinPartitionVal(myInt, CompositionLen, MinVal, (unsigned int) (-1))) == (unsigned int)(-1)) // Increase the MinVal to the minimum that is feasible.
return;
std::vector<unsigned int> v(CompositionLen);
int pos = 0;
const int last = CompositionLen - 1;
for (unsigned int i = 1; i <= last; ++i) // Generate the initial composition
v[i] = MinVal;
unsigned int MaxVal = myInt - MinVal * last;
v[0] = MaxVal;
do
{
DispVector(v);
if (pos == last)
{
if (v[last] == MaxVal)
break;
for (--pos; v[pos] == MinVal; --pos); //Search for the position of the Least Significant non-MinVal (not including the Least Significant position / the last position).
//std::cout << std::setw(pos * 3 + 1) << "" << "v" << std::endl; //DEBUG
--v[pos++];
if (pos != last)
{
v[pos] = v[last] + 1;
v[last] = MinVal;
}
else
v[pos] += 1;
}
else
{
--v[pos];
v[++pos] = MinVal + 1;
}
} while (true);
}
此函数的示例输出为：
GenCompositions(10,4,1);:
7, 1, 1, 1
6, 2, 1, 1
6, 1, 2, 1
6, 1, 1, 2
5, 3, 1, 1
5, 2, 2, 1
5, 2, 1, 2
5, 1, 3, 1
5, 1, 2, 2
5, 1, 1, 3
4, 4, 1, 1
4, 3, 2, 1
4, 3, 1, 2
4, 2, 3, 1
4, 2, 2, 2
4, 2, 1, 3
4, 1, 4, 1
4, 1, 3, 2
4, 1, 2, 3
4, 1, 1, 4
3, 5, 1, 1
3, 4, 2, 1
3, 4, 1, 2
3, 3, 3, 1
3, 3, 2, 2
3, 3, 1, 3
3, 2, 4, 1
3, 2, 3, 2
3, 2, 2, 3
3, 2, 1, 4
3, 1, 5, 1
3, 1, 4, 2
3, 1, 3, 3
3, 1, 2, 4
3, 1, 1, 5
2, 6, 1, 1
2, 5, 2, 1
2, 5, 1, 2
2, 4, 3, 1
2, 4, 2, 2
2, 4, 1, 3
2, 3, 4, 1
2, 3, 3, 2
2, 3, 2, 3
2, 3, 1, 4
2, 2, 5, 1
2, 2, 4, 2
2, 2, 3, 3
2, 2, 2, 4
2, 2, 1, 5
2, 1, 6, 1
2, 1, 5, 2
2, 1, 4, 3
2, 1, 3, 4
2, 1, 2, 5
2, 1, 1, 6
1, 7, 1, 1
1, 6, 2, 1
1, 6, 1, 2
1, 5, 3, 1
1, 5, 2, 2
1, 5, 1, 3
1, 4, 4, 1
1, 4, 3, 2
1, 4, 2, 3
1, 4, 1, 4
1, 3, 5, 1
1, 3, 4, 2
1, 3, 3, 3
1, 3, 2, 4
1, 3, 1, 5
1, 2, 6, 1
1, 2, 5, 2
1, 2, 4, 3
1, 2, 3, 4
1, 2, 2, 5
1, 2, 1, 6
1, 1, 7, 1
1, 1, 6, 2
1, 1, 5, 3
1, 1, 4, 4
1, 1, 3, 5
1, 1, 2, 6
1, 1, 1, 7
加入第 3 个限制（元素的最大值）后，函数的复杂度显着增加。此扩展功能如下所列：
void GenCompositions(unsigned int myInt, unsigned int CompositionLen, unsigned int MinVal, unsigned int MaxVal)
{
if ((MaxVal = MaxPartitionVal(myInt, CompositionLen, MinVal, MaxVal)) == 0) //Decrease the MaxVal to the maximum that is feasible.
return;
if ((MinVal = MinPartitionVal(myInt, CompositionLen, MinVal, MaxVal)) == (unsigned int)(-1)) //Increase the MinVal to the minimum that is feasible.
return;
std::vector<unsigned int> v(CompositionLen);
unsigned int last = CompositionLen - 1;
unsigned int rem = myInt - MaxVal - MinVal*(last-1);
unsigned int pos = 0;
v[0] = MaxVal; //Generate the most significant element in the initial composition
while (rem > MinVal){ //Generate the rest of the initial composition (the highest in the lexicographic order). Spill the remainder left-to-right saturating at MaxVal
v[++pos] = ( rem > MaxVal ) ? MaxVal : rem; //Saturate at MaxVal
rem -= v[pos] - MinVal; //Deduct the used up units (less the background MinValues)
}
for (unsigned int i = pos+1; i <= last; i++) //Fill with MinVal where the spillage of the remainder did not reach.
v[i] = MinVal;
if (MinVal == MaxVal){ //Special case - all elements are the same. Only the initial composition is possible.
DispVector(v);
return;
}
do
{
DispVector(v);
if (pos == last)
{
for (--pos; v[pos] == MinVal; pos--) { //Search backwards for the position of the Least Significant non-MinVal (not including the Least Significant position / the last position).
if (!pos)
return;
}
//std::cout << std::setw(pos*3 +1) << "" << "v" << std::endl; //Debug
if (v[last] >= MaxVal) // (v[last] > MaxVal) should never occur
{
if (pos == last-1) //penultimate position. //Skip the iterations that generate excessively large compositions (with elements > MaxVal).
{
for (rem = MaxVal; ((v[pos] == MinVal) || (v[pos + 1] == MaxVal)); pos--) { //Search backwards for the position of the Least Significant non-extremum (starting from the penultimate position - where the previous "for loop" has finished). THINK: Is the (v[pos] == MinVal) condition really necessary here ?
rem += v[pos]; //Accumulate the sum of the traversed elements
if (!pos)
return;
}
//std::cout << std::setw(pos * 3 + 1) << "" << "v" << std::endl; //Debug
--v[pos];
rem -= MinVal*(last - pos - 1) - 1; //Subtract the MinValues, that are assumed to always be there as a background
while (rem > MinVal) // Spill the remainder left-to-right saturating at MaxVal
{
v[++pos] = (rem > MaxVal) ? MaxVal : rem; //Saturate at MaxVal
rem -= v[pos] - MinVal; //Deduct the used up units (less the background MinValues)
}
for (unsigned int i = pos + 1; i <= last; i++) //Fill with MinVal where the spillage of the remainder did not reach.
v[i] = MinVal;
continue; //The skipping of excessively large compositions is complete. Nothing else to adjust...
}
/* (pos != last-1) */
--v[pos];
v[++pos] = MaxVal;
v[++pos] = MinVal + 1; //Propagate the change one step further. THINK: Why a CONSTANT value like MinVal+1 works here at all?
if (pos != last)
v[last] = MinVal;
}
else // (v[last] < MaxVal)
{
--v[pos++];
if (pos != last)
{
v[pos] = v[last] + 1;
v[last] = MinVal;
}
else
v[pos] += 1;
}
}
else // (pos != last)
{
--v[pos];
v[++pos] = MinVal + 1; // THINK: Why a CONSTANT value like MinVal+1 works here at all ?
}
} while (true);
}
此扩展函数的示例输出为：
GenCompositions(10,4,1,4);:
4, 4, 1, 1
4, 3, 2, 1
4, 3, 1, 2
4, 2, 3, 1
4, 2, 2, 2
4, 2, 1, 3
4, 1, 4, 1
4, 1, 3, 2
4, 1, 2, 3
4, 1, 1, 4
3, 4, 2, 1
3, 4, 1, 2
3, 3, 3, 1
3, 3, 2, 2
3, 3, 1, 3
3, 2, 4, 1
3, 2, 3, 2
3, 2, 2, 3
3, 2, 1, 4
3, 1, 4, 2
3, 1, 3, 3
3, 1, 2, 4
2, 4, 3, 1
2, 4, 2, 2
2, 4, 1, 3
2, 3, 4, 1
2, 3, 3, 2
2, 3, 2, 3
2, 3, 1, 4
2, 2, 4, 2
2, 2, 3, 3
2, 2, 2, 4
2, 1, 4, 3
2, 1, 3, 4
1, 4, 4, 1
1, 4, 3, 2
1, 4, 2, 3
1, 4, 1, 4
1, 3, 4, 2
1, 3, 3, 3
1, 3, 2, 4
1, 2, 4, 3
1, 2, 3, 4
1, 1, 4, 4
问题：我对元素最大值的限制在哪里出错，导致代码的大小和复杂性增加？
IOW：算法的缺陷在哪里，导致在添加一个简单的<= MaxVal限制后出现这个代码膨胀？可以不递归简化吗？
如果有人想实际编译它，下面列出了辅助函数：
#include <iostream>
#include <iomanip>
#include <vector>
void DispVector(const std::vector<unsigned int>& partition)
{
for (unsigned int i = 0; i < partition.size() - 1; i++) //DISPLAY THE VECTOR HERE ...or do sth else with it.
std::cout << std::setw(2) << partition[i] << ",";
std::cout << std::setw(2) << partition[partition.size() - 1] << std::endl;
}
unsigned int MaxPartitionVal(const unsigned int myInt, const unsigned int PartitionLen, unsigned int MinVal, unsigned int MaxVal)
{
if ((myInt < 2) || (PartitionLen < 2) || (PartitionLen > myInt) || (MaxVal < 1) || (MinVal > MaxVal) || (PartitionLen > myInt) || ((PartitionLen*MaxVal) < myInt ) || ((PartitionLen*MinVal) > myInt)) //Sanity checks
return 0;
unsigned int last = PartitionLen - 1;
if (MaxVal + last*MinVal > myInt)
MaxVal = myInt - last*MinVal; //It is not always possible to start with the Maximum Value. Decrease it to sth possible
return MaxVal;
}
unsigned int MinPartitionVal(const unsigned int myInt, const unsigned int PartitionLen, unsigned int MinVal, unsigned int MaxVal)
{
if ((MaxVal = MaxPartitionVal(myInt, PartitionLen, MinVal, MaxVal)) == 0) //Assume that MaxVal has precedence over MinVal
return (unsigned int)(-1);
unsigned int last = PartitionLen - 1;
if (MaxVal + last*MinVal > myInt)
MinVal = myInt - MaxVal - last*MinVal; //It is not always possible to start with the Minimum Value. Increase it to sth possible
return MinVal;
}
//
// Put the definition of GenCompositions() here....
//
int main(int argc, char *argv[])
{
GenCompositions(10, 4, 1, 4);
return 0;
}
注意：由这些函数生成的组合的（自上而下）字典顺序不是可选的。...也不是跳过“do loop”迭代，它不会生成有效的组合。
解决方案
算法
生成具有有限数量的部件和最小值和最大值的组合的迭代算法并不复杂。固定长度和最小值的结合实际上使事情变得更容易；我们可以始终保持每个部分的最小值，只需移动“额外”值即可生成不同的构图。
我将使用这个例子：
n=15, length=4, min=3, max=5
我们将从创建具有最小值的组合开始：
3,3,3,3
然后我们将剩余值 15 - 12 = 3 分配到各个部分，从第一部分开始，每次达到最大值时向右移动：
5,4,3,3
这是第一个组合。然后，我们将使用以下规则重复转换组合以获得反向字典顺序的下一个组合：
我们从找到值大于最小值的最右边的部分开始每一步。（实际上这可以简化；请参阅此答案末尾的更新代码示例。）如果这部分不是最后一部分，我们从中减去 1，并将其右侧部分加 1，例如：
5,4,3,3
^
5,3,4,3
这就是下一个作品。如果最右边的非最小部分是最后一部分，事情会稍微复杂一些。我们将最后一部分的值减少到最小值，并将“额外”值存储在临时总计中，例如：
3,4,3,5
^
3,4,3,3 + 2
然后我们向左移动，直到找到值大于最小值的下一部分：
3,4,3,3 + 2
^
如果这部分(2)右边的部分数能容纳临时合计加1，我们将当前部分减1，临时合计加1，然后分配临时合计，从部分开始到当前部分的右边：
3,3,3,3 + 3
^
3,3,5,4
这就是我们的下一个作品。如果非最小值部分右侧的部分无法保持临时总计加 1，我们将再次将该部分减少到最小值并将“额外”值添加到临时总计中，并进一步查看左，例如（使用 n=17 的不同示例）：
5,3,4,5
^
5,3,4,3 + 2
^
5,3,3,3 + 3
^
4,3,3,3 + 4
^
4,5,5,3
这就是我们的下一个作品。如果我们向左移动以找到一个非最小值，但到达第一部分却没有找到一个，那么我们已经过了最后一个组合，例如：
3,3,4,5
^
3,3,4,3 + 2
^
3,3,3,3 + 3
?
这意味着那3,3,4,5是最后的作品。
如您所见，这只需要一个组合和临时总计的空间，从右到左迭代每个组合一次以找到非最小部分，并从左到右迭代一次组合以分配临时总计。它创建的所有作品都是有效的，并且按相反的字典顺序排列。
代码示例
我首先将上面解释的算法直接翻译成 C++。找到最右边的非最小部分并在组合上分配值是由两个辅助函数完成的。代码一步一步地遵循解释，但这不是最有效的编码方式。请参阅下面的改进版本。
#include <iostream>
#include <iomanip>
#include <vector>
void DisplayComposition(const std::vector<unsigned int>& comp)
{
for (unsigned int i = 0; i < comp.size(); i++)
std::cout << std::setw(3) << comp[i];
std::cout << std::endl;
}
void Distribute(std::vector<unsigned int>& comp, const unsigned int part, const unsigned int max, unsigned int value) {
for (unsigned int p = part; value && p < comp.size(); ++p) {
while (comp[p] < max) {
++comp[p];
if (!--value) break;
}
}
}
int FindNonMinPart(const std::vector<unsigned int>& comp, const unsigned int part, const unsigned int min) {
for (int p = part; p >= 0; --p) {
if (comp[p] > min) return p;
}
return -1;
}
void GenerateCompositions(const unsigned n, const unsigned len, const unsigned min, const unsigned max) {
if (len < 1 || min > max || n < len * min || n > len * max) return;
std::vector<unsigned> comp(len, min);
Distribute(comp, 0, max, n - len * min);
int part = 0;
while (part >= 0) {
DisplayComposition(comp);
if ((part = FindNonMinPart(comp, len - 1, min)) == len - 1) {
unsigned int total = comp[part] - min;
comp[part] = min;
while (part && (part = FindNonMinPart(comp, part - 1, min)) >= 0) {
if ((len - 1 - part) * (max - min) > total) {
--comp[part];
Distribute(comp, part + 1, max, total + 1);
total = 0;
break;
}
else {
total += comp[part] - min;
comp[part] = min;
}
}
}
else if (part >= 0) {
--comp[part];
++comp[part + 1];
}
}
}
int main() {
GenerateCompositions(15, 4, 3, 5);
return 0;
}
改进的代码示例
实际上，大部分的调用FindNonMinPart都是不必要的，因为在你重新分配了值之后，你确切地知道最右边的非最小部分在哪里，并且不需要再次搜索它。重新分配额外值也可以简化，不需要函数调用。
下面是考虑到这些因素的更有效的代码版本。它在零件中左右移动，搜索非最小零件，重新分配额外价值并在完成后立即输出作品。它明显比第一个版本快（尽管调用DisplayComposition显然占用了大部分时间）。
#include <iostream>
#include <iomanip>
#include <vector>
void DisplayComposition(const std::vector<unsigned int>& comp)
{
for (unsigned int i = 0; i < comp.size(); i++)
std::cout << std::setw(3) << comp[i];
std::cout << std::endl;
}
void GenerateCompositions(const unsigned n, const unsigned len, const unsigned min, const unsigned max) {
// check validity of input
if (len < 1 || min > max || n < len * min || n > len * max) return;
// initialize composition with minimum value
std::vector<unsigned> comp(len, min);
// begin by distributing extra value starting from left-most part
int part = 0;
unsigned int carry = n - len * min;
// if there is no extra value, we are done
if (carry == 0) {
DisplayComposition(comp);
return;
}
// move extra value around until no more non-minimum parts on the left
while (part != -1) {
// re-distribute the carried value starting at current part and go right
while (carry) {
if (comp[part] == max) ++part;
++comp[part];
--carry;
}
// the composition is now completed
DisplayComposition(comp);
// keep moving the extra value to the right if possible
// each step creates a new composition
while (part != len - 1) {
--comp[part];
++comp[++part];
DisplayComposition(comp);
}
// the right-most part is now non-minimim
// transfer its extra value to the carry value
carry = comp[part] - min;
comp[part] = min;
// go left until we have enough minimum parts to re-distribute the carry value
while (part--) {
// when a non-minimum part is encountered
if (comp[part] > min) {
// if carry value can be re-distributed, stop going left
if ((len - 1 - part) * (max - min) > carry) {
--comp[part++];
++carry;
break;
}
// transfer extra value to the carry value
carry += comp[part] - min;
comp[part] = min;
}
}
}
}
int main() {
GenerateCompositions(15, 4, 3, 5);
return 0;
}
推荐阅读
- java - Selenium - 如何获得以下兄弟姐妹？
- apache-spark - 在 pyspark 数据帧中将 132K 转换为 132000 和 224.4M 转换为 224,400,000
- c++ - 循环依赖和 unique_ptr
- swiftui - Form 和 List 两次渲染子视图
- node.js - 如何使用 reactjs 组件将数据数组发送到 mongodb？
- api - 我应该使用哪个 google oauth Playground API 来获取带有名称、用户照片和电子邮件的令牌？
- postgresql - pgAdmin 抛出错误保存属性无法连接服务器超时已过期连接到 AWS Lightsail 中的 Postgresql
- c - 为什么我的代码中出现分段错误？无法调试，请解释错误
- python - 将指标/结果组合成一个数据框 python
- java - 请求标头编码更改为空正文