具有递归函数的嵌套循环

Question

有人可以帮助我如何使用 recursive_loops 实现以下版本的nested_loops吗？我能够使用nested_loops 生成我想要的确切输出，但它始终限制为 3 个循环。我想让循环数动态化，假设有 10 个循环。因此我想使用 recursive_loops 来实现它。下面是nested_loops的工作代码，但无法使用recursive_loops生成类似的输出。预先感谢。

驱动程序代码：

 #include <iostream>
 #include <vector>
 
 using namespace std;
 
 void nested_loops(unsigned int loop, const unsigned int &maxloop, 
           unsigned int no, const unsigned int &maxno, 
           unsigned int sum, const unsigned int &matchsum,
           vector<unsigned int> &pos, vector<vector<unsigned int>> &positions);
           
 void recursive_loops(unsigned int loop, const unsigned int &maxloop, 
           unsigned int no, const unsigned int &maxno, 
           unsigned int sum, const unsigned int &matchsum,
           vector<unsigned int> &pos, vector<vector<unsigned int>> &positions);
           
 void show_positions(const vector<vector<unsigned int>> &positions);
 
 int main()
 {
    vector<vector<unsigned int>> positions;
    vector<unsigned int> pos;

    nested_loops(1, 3, 1, 20, 1, 15, pos, positions);
    cout << "\nPositions size after nested_loops:" << positions.size() << endl;
    show_positions(positions);
    
    
    positions.clear();
    pos.clear();
    
    recursive_loops(1, 3, 1, 20, 1, 15, pos, positions);
    cout << "\nPositions size after recursive_loops:" << positions.size() << endl;
    show_positions(positions);
    
    return 0;
 }
 
 void show_positions(const vector<vector<unsigned int>> &positions)
 {
    vector<unsigned int> pos;
    for(int i=0; i<positions.size(); ++i)
    {
        cout << endl;
        pos = positions[i];
        for(int j=0; j<pos.size(); ++j)
        {
            cout << " " << pos[j];
        }
    }   
    cout << endl << endl;   
 }

嵌套循环：

void nested_loops(unsigned int loop, const unsigned int &maxloop, 
           unsigned int no, const unsigned int &maxno, 
           unsigned int sum, const unsigned int &matchsum,
           vector<unsigned int> &pos, vector<vector<unsigned int>> &positions)
{
    for(int i1=no; i1<maxno-2; ++i1)
    {
        
    for(int i2=i1+1; i2<maxno-1; ++i2)
    {
        
    for(int i3=i2+1; i3<maxno; ++i3)
    {
        sum=i1+i2+i3;
        
        if(sum==matchsum)
        {
            pos.clear();
            pos.push_back(i1);
            pos.push_back(i2);
            pos.push_back(i3);
            
            positions.push_back(pos);
            
            break;
            
        }
        
    } } }
    
}

递归循环：

void recursive_loops(unsigned int loop, const unsigned int &maxloop, 
           unsigned int no, const unsigned int &maxno, 
           unsigned int sum, const unsigned int &matchsum,
           vector<unsigned int> &pos, vector<vector<unsigned int>> &positions)
{
    pos.push_back(no);
    
    if(loop == maxloop)
    {
        if(sum+no == matchsum)
        {
            positions.push_back(pos);
        }
        return;
    }
    else
    {
        recursive_loops(loop+1, maxloop, no+1, maxno, sum+no+1, matchsum, pos, positions);
    
        if(no < maxno)
        {
            if(sum+no < matchsum)  
            {
                pos.pop_back();
                
                for(int i=no; no+i<maxno && sum+no+i<=matchsum; ++i)
                {
                    recursive_loops(loop+1, maxloop, no+i, maxno, sum+no+i, matchsum, pos, positions);
                    pos.pop_back();
                }
            }
        }
    }
    
    //pos.pop_back();
}

输出：（期望两个函数调用有相同的输出） 每行的数字总和等于 15，并且数字始终是递增的。

Positions size after nested_loops:12

 1 2 12
 1 3 11
 1 4 10
 1 5 9
 1 6 8
 2 3 10
 2 4 9
 2 5 8
 2 6 7
 3 4 8
 3 5 7
 4 5 6


Positions size after recursive_loops:3

 1 2 6
 1 2 6
 1 4 5

Answer 1

您的代码正在做的是查找具有给定总和的 [1, ..., n] 的 3 个组合。所以你的问题归结为“你如何递归地找到n个项目的k组合？”

组合确实表现出递归结构。可以通过按排序顺序增量构建组合来递归生成组合。要生成一组 n 项目的所有 k 组合，您可以从部分组合 P 开始，它是已选择项目的子集。如果 P 的长度为 m，其中 m 小于 k，则下一步是通过附加由项目形成的长度 k 减去 m 的所有可能组合来完成 P位于 P 的最后一个元素之后。这可确保组合按排序顺序构造且不会重复。

代码如下：

#include <iostream>
#include <vector>

using vectors = std::vector<std::vector<int>>;

// helper function to give the recursive call
// the signature we want ...
void combinations_aux(
        int n, int k, int start, std::vector<int>& current, vectors& result) {

    // Base case: if the combination has the required size, add it to the result
    if (current.size() == k) {
        result.push_back(current);
        return;
    }

    // Recursive case: try all possible next elements
    for (int i = start; i <= n; ++i) {
        current.push_back(i);
        combinations_aux(n, k, i + 1, current, result);
        current.pop_back();                   
    }

}

std::vector<std::vector<int>> combinations(int n, int k) {
    std::vector<std::vector<int>> result;
    std::vector<int> current;
    combinations_aux(n, k, 1, current, result);
    return result;
}

vectors triples_of_given_sum(int n, int sum) {
    vectors output;
    for (auto combo : combinations(n, 3)) {
        if (combo[0] + combo[1] + combo[2] == sum) {
            output.push_back(combo);
        }
    }
    return output;
}

int main() {

    for (const auto& tri : triples_of_given_sum(20, 15)) {
        std::cout << tri[0] << " " << tri[1] << " " << tri[2] << "\n";
    }

    return 0;
}