Menu
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.
751
Algorithm
An iterative algorithm to generate compositions with restricted number of parts and mininum and maximum value is not that complicated. The combination of fixed length and minimum value actually makes things easier; we can keep the minimum value in every part at all times, and just move the "extra" value around to generate the different compositions.
I'll be using this example:
n=15, length=4, min=3, max=5
We will start by creating a composition with minimum values:
3,3,3,3
and then we distribute the left-over value, 15 - 12 = 3, over the parts, starting at the first part and moving right each time we reach the maximum value:
5,4,3,3
This is the first composition. We will then repeatedly transform the composition to get the reverse-lexicographically next one, using these rules:
We start each step by finding the right-most part whose value is greater than the minimum value. (Actually this can be simplified; see updated code example at the end of this answer.) If this part is not the last part, we subtract 1 from it, and add 1 to the part to the right of it, e.g.:
5,4,3,3
^
5,3,4,3
and that is the next composition. If the right-most non-minimum part is the last part, things are a little more complicated. We reduce the value of the last part to the minimum, and store the "extra" value in a temporary total, e.g.:
3,4,3,5
^
3,4,3,3 + 2
We then move further left until we find the next part whose value is greater than the minimum value:
3,4,3,3 + 2
^
If the number of parts to the right of this part (2) can hold the temporary total plus 1, we subtract 1 from the current part, and add 1 to the temporary total, and then distribute the temporary total, starting at the part to the right of the current part:
3,3,3,3 + 3
^
3,3,5,4
and that is our next composition. If the parts to the right of the non-minimum part had not been able to hold the temporary total plus 1, we would have again reduced that part to the minimum value and added the "extra" value to the temporary total, and looked further left, e.g. (using a different example with 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
and that is our next composition. If we are moving left to find a non-minimum value, but reach the first part without having found one, we are past the last composition, e.g.:
3,3,4,5
^
3,3,4,3 + 2
^
3,3,3,3 + 3
?
That means that 3,3,4,5 was the last composition.
As you see this needs only space for one composition and the temporary total, iterates over each composition once from right to left to find non-minimum parts, and iterates over the composition once from left to right to distribute the temporary total. All the compositions it creates are valid, and in reverse lexicographical order.
Code example
I first wrote this straightforward translation into C++ of the algorithm explained above. Finding the right-most non-minimum part and distributing values over the composition is done by two helper functions. The code follows the explanation step by step, but that is not the most efficient way to code it. See further below for an improved version.
#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;
}
Improved code example
Actually, most of the calls to FindNonMinPart are unnecessary, because after you've re-distributed values, you know exactly where the right-most non-minimum part is, and there's no need to search for it again. Re-distributing the extra value can also be simplified, with no need for a function call.
Below is a more efficient code version that takes these things into account. It walks left and right through the parts, searching for non-minimum parts, re-distributing extra value and outputting compositions as soon as they are completed. It is noticably faster than the first version (although the calls to DisplayComposition obviously take up most of the time).
#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;
}
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
