Best way to do multiply nested loops

[dosterpf]

I'm working on a project, and I have an arbitrarily high number of dimensions N. I want to create a loop over all combinations for each of these N dimensions from say 0 to M-1. So something like:

for(i1=0;i1<M;++i1){
for(i2=0;i2<M;++i2){
.
.
.
for(iN=0;iN<M;++iN){
check for some condition, if condition satsified, we add vector
[i1, ..., iN] to a list
}
.
.
.
}
}

Right now I am doing this with recursion, but N may get to be VERY large, so I do not want to have to worry about recursion limits on different machines and whatnot. Anyone know a good way to do this looping? I know that this type of loop for arbitrarily large N,M will have more operations than are reasonable, but there is other types of compression and whatnot, so don't really worry about that issue. Thank you for all of the help.

[JosAH]

So you want C(n, k) for, say, n == 4 and k == 2 so you want the tuples
01, 02, 03, 12, 13 and 23, right?

Note that the number at position i is less than the number at position i+1 and
that the number at position j must be <= n-(k-j). If you start at the first
combination (here: 01) and start at the rightmost position, do an increment until
you can satisfy both of the above conditions, you can enumerate all
combinations iteratively in a single loop.

kind regards,

Jos

[dosterpf]

Thanks for the reply, but not quite what I am doing. I'm not taking combinations nor permutations or anything like that. Essentially, I just want a good way to have an arbitrarily large loop. Just like the code I wrote. I want N successive nested for loops, each of which goes from from 0 to M-1 (so N^M total times in the inside loop).

So, for N=2 I'd have

for(i1=0;i1<M;i1++)
for(i2=0;i2<M;i2++)

and for N=3 I'd have
for(i1=0;i1<M;i1++)
for(i2=0;i2<M;i2++)
for(i3=0;i3<M;i3++)

etc.

My N is a command line parameter, since my dimensions my change from one run to the next. So I cannot "hard code" this set of loops.

It's a relatively easy recursion... but I was hoping someone might know a "trick" that my be more "C++ optimized" since recursion for large N may run into some issues. Thanks.

So you want C(n, k) for, say, n == 4 and k == 2 so you want the tuples
01, 02, 03, 12, 13 and 23, right?

Note that the number at position i is less than the number at position i+1 and
that the number at position j must be <= n-(k-j). If you start at the first
combination (here: 01) and start at the rightmost position, do an increment until
you can satisfy both of the above conditions, you can enumerate all
combinations iteratively in a single loop.

kind regards,

Jos

[AdrianH]

Thanks for the reply, but not quite what I am doing. I'm not taking combinations nor permutations or anything like that. Essentially, I just want a good way to have an arbitrarily large loop. Just like the code I wrote. I want N successive nested for loops, each of which goes from from 0 to M-1 (so N^M total times in the inside loop).

So, for N=2 I'd have

for(i1=0;i1<M;i1++)
for(i2=0;i2<M;i2++)

and for N=3 I'd have
for(i1=0;i1<M;i1++)
for(i2=0;i2<M;i2++)
for(i3=0;i3<M;i3++)

etc.

My N is a command line parameter, since my dimensions my change from one run to the next. So I cannot "hard code" this set of loops.

It's a relatively easy recursion... but I was hoping someone might know a "trick" that my be more "C++ optimized" since recursion for large N may run into some issues. Thanks.

Recursion is not a bad thing. For most compilers, this is not a problem. In fact many compiler optimisers will take something that is recursive and may be able to unwind it to somewhat, and if not, your recursion depth is limited only to your stack size which you can increase if you want to. Since you are using an arbitrarily nesting depth, recursion is probably the best way to go for its dynamic ability to handle the situation.

To explicitly unwind the recursion would require an upper bound, and to go beyond it would require recursion. If this is really what you want, try BOOST’s MPL preprocessor language. I’m working on an update for it currently to speed it up (it is supposed to be quite fast already) and make it more readable, but it won’t be complete for at least a month. BOOST’s current version is capable of writing many (close to) arbitrary things for you, given that you write the preprocessor code to do it.

In all honesty though, I really don’t think that it is worth it. What issues do you see that could occur? Blowing the stack a little sooner? Making it slightly slower? Remember, optimisers are quite powerful now. You may be just wasting your time.


Adrian