Non-recursive enumeration of triply restricted positive integer compositions
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;
}