Geo*_*son 7 c++ algorithm combinatorics
After creating an iterative (non-recursive) function, that enumerates doubly restricted compositions of positive integers in a lexicographic order, for a microcontroller with a very small amount of RAM (but large EPROM), I had to expand the number of restrictions to 3, namely to:
The original function, that generates the doubly restricted compositions is listed below:
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);
}
The sample output of this funtion is:
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
After adding the 3rd restriction (on the maximum value of elements), the complexity of the function increased significantly. This expanded function is listed below:
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);
}
The sample output of this expanded funtion is:
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
QUESTION: Where did my implementation of the restriction on the maximum value of elements go wrong, to cause such increase in the size and complexity of the code?
IOW: Where is the flaw in the algorithm, which causes this code bloat to appear after adding one simple <= MaxVal restriction? Can it be simplified without recursion?
If someone wants to actually compile this, the helper functions are listed below:
#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;
}
NOTE: the (top-bottom) lexicographic order of the compositions generated by these functions is not optional. ...nor is the skipping of the "do loop" iterations, that do NOT generate valid compositions.
算法
生成具有有限数量的部件以及最小值和最大值的组合的迭代算法并不那么复杂。固定长度和最小值的结合实际上让事情变得更容易；我们可以始终保持每个部分的最小值，并且只需移动“额外”值即可生成不同的组合。
我将使用这个例子：
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++。找到最右边的非最小部分并在组合上分配值是由两个辅助函数完成的。代码一步步遵循解释，但这并不是最有效的编码方式。有关改进版本，请参阅下文。
n=15, length=4, min=3, max=5
改进的代码示例
实际上，大多数调用FindNonMinPart都是不必要的，因为在重新分配值之后，您就知道最右边的非最小值部分在哪里，并且无需再次搜索它。重新分配额外值也可以得到简化，无需函数调用。
下面是考虑了这些因素的更有效的代码版本。它在零件中左右行走，搜索非最小零件，重新分配额外值并在完成后立即输出组合。它明显比第一个版本快（尽管调用DisplayComposition显然占用了大部分时间）。
3,3,3,3