c++ - 三重限制正整数组合的非递归枚举

Question

创建迭代(非递归)函数后，枚举 加倍受限 compositions of positive integers按照字典顺序，对于 RAM 非常少(但 EPROM 很大)的微 Controller ，我不得不将限制数量扩大到 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

添加第三个限制(对元素的最大值)后，函数的复杂度显着增加。下面列出了这个扩展的功能:

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”迭代，它不会生成有效的组合。

Answer 1

算法

生成具有有限数量的部件和最小值和最大值的组合的迭代算法并不那么复杂。固定长度和最小值的组合实际上使事情变得更容易；我们可以始终保持每个部分的最小值，只需移动“额外”值即可生成不同的组合。

我将使用这个例子:

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 的电话是不必要的，因为在您重新分配值之后，您确切地知道最右边的非最小部分在哪里，并且无需再次搜索它。重新分配额外的值也可以简化，不需要函数调用。

下面是一个更有效的代码版本，它考虑了这些事情。它在零件中左右走动，搜索非最小零件，重新分配额外的值(value)并在完成后立即输出作品。它明显比第一个版本快(尽管对 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;
}