C++ variable number of nested loops

Question

I want to make a function that, depending on the depth of nested loop, does this:

if depth = 1:

for(i = 0; i < max; i++){
    pot[a++] = wyb[i];
}

if depth = 2:

for(i = 0; i < max; i++){
    for( j = i+1; j < max; j++){
        pot[a++] = wyb[i] + wyb[j];
    }
}

if depth = 3:

for(i = 0; i < max; i++){
    for( j = i+1; j < max; j++){
        for( k = j+1; k < max; k++){
            pot[a++] = wyb[i] + wyb[j] + wyb[k];
        }
    }
}

and so on.

So the result would be:

depth = 1

pot[0] = wyb[0]
pot[1] = wyb[1]
...
pot[max-1] = wyb[max-1]

depth = 2, max = 4

pot[0] = wyb[0] + wyb[1]
pot[1] = wyb[0] + wyb[2]
pot[2] = wyb[0] + wyb[3]
pot[3] = wyb[1] + wyb[2]
pot[4] = wyb[1] + wyb[3]
pot[5] = wyb[2] + wyb[3]

I think you get the idea. I can't think of a way to do this neatly.

Could someone present an easy way of using recursion (or maybe not?) to achieve this, keeping in mind that I'm still a beginner in c++, to point me in the right direction?

Thank you for your time.

The general answer to "variable nesting of loops" is to use recursion. — Cheers and hth. - Alf
– Cheers and hth. - Alf, Commented Aug 5, 2014 at 12:03

Jarod42 · Accepted Answer · 2014-08-05 12:35:07Z

3

You may use the std::next_permutation to manage the combinaison:

std::vector<int> compute(const std::vector<int>& v, std::size_t depth)
{
    if (depth == 0 || v.size() < depth) {
        throw "depth is out of range";
    }
    std::vector<int> res;
    std::vector<int> coeffs(depth, 1);
    coeffs.resize(v.size(), 0); // flags is now {1, .., 1, 0, .., 0}

    do {
        int sum = 0;
        for (std::size_t i = 0; i != v.size(); ++i) {
            sum += v[i] * coeffs[i];
        }
        res.push_back(sum);
    } while (std::next_permutation(coeffs.rbegin(), coeffs.rend()));
    return res;
}

Live example

answered Aug 5, 2014 at 12:35

Jarod42

228k15 gold badges214 silver badges352 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Cheers and hth. - Alf Over a year ago

+1 for noticing that it was permutations and suggesting a standard library solution.

tohava · Accepted Answer · 2014-08-05 12:37:13Z

0

Simplified recursive version:

int *sums_recursive(int *pot, int *wyb, int max, int depth) {
    if (depth == 1) {
        while (max--)
            *pot++ = *wyb++;
        return pot;
    }
    for (size_t i = 1; i <= max - depth + 1; ++i) {
        int *pot2 = sums_recursive(pot, wyb + i, max - i, depth - 1);
        for (int *p = pot ; p < pot2; ++p) *p += wyb[i - 1];
        pot = pot2;
    }
    return pot;
}

Iterative version:

void sums(int *pot, int *wyb, int max, int depth) {
    int maxi = 1;
    int o = 0;
    for (int d = 0; d < depth; ++d) { maxi *= max; }
    for (int i = 0; i < maxi; ++i) {
        int i_div = i;
        int idx = -1;
        pot[o] = 0;
        int d;
        for (d = 0; d < depth; ++d) {
            int new_idx = i_div % max;
            if (new_idx <= idx) break;
            pot[o] += wyb[new_idx];
            idx = new_idx;
            i_div /= max;
        }
        if (d == depth) o++;
    }
}

edited Aug 5, 2014 at 12:37

answered Aug 5, 2014 at 11:57

tohava

5,4321 gold badge30 silver badges48 bronze badges

1 Comment

Jarod42 Over a year ago

You may use const int *wyb.

Collectives™ on Stack Overflow

C++ variable number of nested loops

2 Answers 2

1 Comment

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related