C++ dynamic nested for loop

Question

I am trying to compute the following quantity with a dynamic number of loops. The pseudo-code looks like

When k = 1,

for (x1 =0;x1<=nmax[1];x1++){
    a = a + x1 * (x1>upper[1]);
}

When k = 2

for (x1 =0;x1<=nmax[1];x1++){
    for (x2 =0;x2<=nmax[2];x2++){
        a = a + x1 * (x1<upper[1]) * x2 *(x1+x2>upper[2]);
    }
}

When k = 3

for (x1 =0;x1<=nmax[1];x1++){
    for (x2 =0;x2<=nmax[2];x2++){
        for (x3 =0;x3<=nmax[3];x3++){
            a = a + x1 * (x1<upper[1]) * x2 *(x1+x2<upper[2]) * x3 *(x1+x2+x3>upper[3]);
        }
    }
}

nmax and upper are predefined vector.

To illustrate the logic behind the boolean expressions, as an example, as k increases, the boolean expression develops as follows. For the first one to the second before the last, it's <; whereas the last one uses >.

(x1>upper[1])
(x1<upper[1]) AND (x1+x2>upper[2]) 
(x1<upper[1]) AND (x1+x2<upper[2]) AND (x1+x2+x3>upper[3])
(x1<upper[1]) AND (x1+x2<upper[2]) AND (x1+x2+x3<upper[3]) AND (x1+x2+x3+X4>upper[4])
(x1<upper[1]) AND (x1+x2<upper[2]) AND (x1+x2+x3<upper[3]) AND (x1+x2+x3+x4<upper[4]) AND (x1+x2+x3+x4+x5>upper[5])

Is there a way to write a function that use k as an argument to achieve the above?

You want to generate all possible x1, x2, ... xn and calculate the value. You should use en.wikipedia.org/wiki/Backtracking — SashaMN
– SashaMN, Commented Jan 17, 2016 at 5:49
Initialize a vector<int> x of size k to all zeros. In a loop, add 1 to x[0]; if this causes it to go over nmax, reset it to 0 and add one to x[1] (and if x[1] goes over as a result, reset it to 0 and increment x[2], and so on). Basically, increment with carry. For each state of x thus computed, run a second nested loop to calculate the sum and update a. — Igor Tandetnik
– Igor Tandetnik, Commented Jan 17, 2016 at 5:51
Thanks for the reply. What do you mean by "run a second nested loop"? — a maras
– a maras, Commented Jan 17, 2016 at 5:55

arubirate · Accepted Answer · 2016-01-18 07:46:00Z

1

I recommend you to use recursive function.

int k;
int nestedLoop(int cur, int stValue) {
   int ret = 0;
   if( cur > k ) return 1;
   for(x=0;x<=nmax[cur];x++) {
       if( cur % 2 ) {
           ret = ret + x * 
               (stValue+x < upper[cur]) * nestedLoop(cur+1, stValue + x); 
       } else {
           ret = ret + x *
               (stValue+x > upper[cur]) * nestedLoop(cur+1, stValue + x);
       }
   }
   return ret
}

I'm sorry for that I cannot test it is correct right now. But the way what you want is acheived by sort of this method.

Just for simple case

int k = 3;
int nestedloop(int cur) {
    if(cur > k) { return 1; }
    int ret = 0;
    int i;
    for(int i=1;i<=5;i++) {
        ret = ret + i * nestedloop(cur+1);
    }
    return ret == 0 ? 1 : ret;
}

this code is same to next code.

for(int i=1;i<=5;i++){
    for(int j=1;j<=5;j++){
        for(int k=1;k<=5;k++){
            ret = ret + i * j * k;
        }
    }
}

edited Jan 18, 2016 at 7:46

answered Jan 17, 2016 at 6:31

arubirate

876 bronze badges

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

5 Comments

a maras Over a year ago

Thanks a lot for the solution. I have a question. The condition (cur % 2) looks odd. The boolean expression uses > only for the last x. For example, for k=3, it's (x1<upper[1]) *(x1+x2<upper[2]) *(x1+x2+x3>upper[3]); for k =4, it's (x1<upper[1]) *(x1+x2<upper[2]) *(x1+x2+x3<upper[3])*(x1+x2+x3+x4>upper[4])

arubirate Over a year ago

Oh, I see. i misunderstand your code. but I think last operator is a little different. for that, you should change condition parts.

a maras Over a year ago

I tried your approach but it keeps return 1. Doesn't seem work.

a maras Over a year ago

I did add the return ret. But it stills returns 1 in all cases.

arubirate Over a year ago

Really? I do simple case, but it works. I edit my post to add my simple code.

Collectives™ on Stack Overflow

C++ dynamic nested for loop

1 Answer 1

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related