c++ - Nested loops with recursive functions - Stack Overflow

admin管理员组

文章数量:1122832

Could some one help me how to implement below version of nested_loops with recursive_loops? I was able to generated the exact output what I want using nested_loops, but it is always limited to 3 loops. I want to make the number of loops dynamic, let's assume 10 loops. Hence I want to implement it using recursive_loops. Below is the working code of nested_loops but unable to generate similar output using recursive_loops. Thanks in advance.

Driver code:

 #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;   
 }

nested_loops:

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;
            
        }
        
    } } }
    
}

recursive_loops:

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();
}

Output: (expecting same output for both function calls) Sum of numbers matches to 15 for every line and numbers are always incremental.

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

Could some one help me how to implement below version of nested_loops with recursive_loops? I was able to generated the exact output what I want using nested_loops, but it is always limited to 3 loops. I want to make the number of loops dynamic, let's assume 10 loops. Hence I want to implement it using recursive_loops. Below is the working code of nested_loops but unable to generate similar output using recursive_loops. Thanks in advance.

Driver code:

 #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;   
 }

nested_loops:

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;
            
        }
        
    } } }
    
}

recursive_loops:

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();
}

Output: (expecting same output for both function calls) Sum of numbers matches to 15 for every line and numbers are always incremental.

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

• c++
• recursion
• nested-loops

Share Improve this question Follow edited Nov 23, 2024 at 5:28 John Kugelman 361k6969 gold badges546546 silver badges591591 bronze badges asked Nov 23, 2024 at 1:21 musk'smusk's 12322 silver badges88 bronze badges 3

• Isn't there a math solution to this specific problem? You can probably use stars and bars and avoid loops entirely. – Herbert The Bird Commented Nov 23, 2024 at 4:29
• Is it mandatory that recursive_loops() has exactly that signature (in particular the types of arguments)? I ask because, by doing it as you have, you have made the problem significantly harder than it needs to be (which probably contributes to your failure to get that function working as you require). – Peter Commented Nov 23, 2024 at 10:53
• @peter - I just need output based on the input, function arguments does not matter. – musk's Commented Nov 24, 2024 at 2:33

Add a comment  | 

2 Answers 2

Sorted by: Reset to default 1

What your code is doing is finding the 3-combinations of [1, ..., n] that have a given sum. So your question boils down to "How do you find the k-combinations of n items recursively?"

Combinations do exhibit recursive structure. They can be generated recursively by building them incrementally in sorted order. To generate all k-combinations of a set of n items, you start with a partial combination P, which is a subset of items already selected. If the length of P is m, where m is less than k, the next step is to complete P by appending all possible combinations of length k-m formed from the items that come after the last element of P. In practice, with a recursive call, this can be done one item at a time, rather than literally returning all the sub-combinations and appending, etc., but it is the same idea.

Code below. In the following current is the partial combination P discussed above.

#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();                   
    }

}

vectors 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 (const 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;
}

Note: this proposal doesn't directly answer the question since it doesn't need recursion.

However for answering the actual problem, one has just to observe that we need to enumerate numbers of DIM digits (3 in your example) in basis BASE (20 in your example) and then check that the sum of the digits matches the required value (15 for instance).

So the problem becomes easier; the only trick when enumerating the number is (1) to take carries into account and (2) make sure that the successive digits are always increasing.

The solution can be used for different DIM and BASE. DIMis sowewhat the equivalent of the number of inner loops in your approach.

#include <cstdint>
#include <array>
#include <numeric>
#include <iostream>
#include <iomanip>

int main()
{
    using digit_t = uint16_t;
    
    const digit_t     BASE = 20;
    const std::size_t DIM  = 3;

    uint64_t checksum = 15;
    
    using number_t = std::array<digit_t,DIM>;

    number_t number;
    
    for (digit_t d=0; d<number.size(); d++) { number[d] = number.size()-d; }
       
    auto found = [] (number_t const& number)  
    {
        for (int i=number.size()-1; i>=0; i--)
        {
            std::cout << std::setw(2) << number[i] << " ";
        }
        std::cout << "\n"; 
    };  
       
    // We iterate all required numbers.   
    bool done = false;
    while (not done)
    {
        // compute the sum of the digits
        if (std::accumulate (number.begin(), number.end(), uint64_t{}) == checksum) 
        {
            // ok we found a matching number
            found (number);
        }
        
        // increase the number
        bool carry = false;
        for (std::size_t k=0; k<DIM; k++)
        {
            number[k] ++;

            // we may have a carry to handle
            if (number[k]==BASE-k)
            {
                carry = true;
                
                // if the last digit reached the max number, we are done.
                if (k==DIM-1)  { done = true; } 
                else
                {                
                    // we reinit the digit; we will make sure after that we have increasing numbers
                    number[k] = 0;
                }
            }
            else
            {
                break;
            }
        }
        
        if (carry)
        {
            // we had a carry, so we make sure that the digits are strictly increasing again.
            for (std::size_t i=number.size()-1; i>0; i--)
            {
                if (number[i]>=number[i-1])  { number[i-1] = number[i] + 1; }
            }
        }
    }
}

Possible output for DIM=3, BASE=20 and checksum=15:

 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 

Possible output for DIM=4, BASE=8 and checksum=15:

 1  2  5  7 
 1  3  4  7 
 1  3  5  6 
 2  3  4  6 

Demo

本文标签： cNested loops with recursive functionsStack Overflow