Generating dynamically nested loops

Introduction

Certain problems require a deep level of nested loops such as problems related to combinotronics. If the number of nesting is a variable it is a bit tricky to come up with a solution. The solution listed below shows how a solution that needs to use a series of nested loops can be implemented using a single level nested loop.

A simple example of generating all possible values

for (int r=1;r<=3;r++)
   for (int s=1;s<=3;s++)
      for (int t=1;t<=3;t++)
         cout << r << s << t << endl;  // print(r,s,t) 
// output 
111
112
113
121
122
123
131
132
133
211
212
213
221
222
223
231
232
233
311
312
313
321
322
323
331
332
333 

What if you want to do this for 9 variables. Here we will need to use 9 levels of nested variables.

Imagine if this was for 100. Impossible right.

If we look at how the nested loops work, we see that the inner most loop works most of time and the upper loops are needed only when we run out of values in the inner loops.

To convert this into a dynamic nested loop we can represent the different loop variables in an array. For simplicity lets assume that the upper bound of these variables are a constant as in the above example.

To implement a dynamic nested loop we need to increment the inner most loop variable until we run out values. Only then do we need to look at changing the upper level loop variables.

Sample Dynamic loop

Given here is a solution that shows how a dynamic loop can be implemented. The code is written in C++ and can be easily converted to any other language such as C#, Java.

The code below how this can be done for 9 levels.

MAXROWS contains the number of levels

MAXVALUES contains the maximum combination for a given nested variables.

arrs[] contains the separate loop variables.

display[] contains the values to be displayed on screen

#include <iostream>
#define MAXROWS 9
#define MAXVALUES 9

using namespace std;
char display[] = {'1','2','3','4','5','6','7','8','9'};

int main() {

    int arrs[MAXROWS];  // represent the different variables in the for loops
                          
    bool status = false;

    for (int r=0;r<MAXROWS;r++)
        arrs[r] = 0;  // Initialize values

    while (!status) { 
    
        int total = 0;
        // calculate total for exit condition
        for (int r=0;r<MAXROWS;r++)
            total +=arrs[r];
        // test for exit condition
        if (total == (MAXVALUES-1)*MAXROWS)
            status = true;

        // printing
        for (int r=0;r<MAXROWS;r++)
            cout << display[arrs[r]]; // print(arrs[r])
        cout << endl;  // print(endline)

        // increment loop variables
            bool change = true;
        int r = MAXROWS-1;  // start from innermost loop
        while (change && r>=0) {
            // increment the innermost variable and check if spill overs
            if (++arrs[r] > MAXVALUES-1) {        
                arrs[r] = 0;  // reintialize loop variable
                // Change the upper variable by one
                // We need to increment the immediate upper level loop by one
                change = true;
            }
            else
                change = false; // Stop as there the upper levels of the loop are unaffected

            // We can perform any inner loop calculation here arrs[r]

            r=r-1;  // move to upper level of the loop

        }
        
    }

    char ch;
    cin >> ch;

    return 0;
}

Here the variable total is used to calculate when to stop, in the original example we stop after we print 333, the total of the three variables should be 3+3+3=9

Since a zero based index is used in the coding, we reduce 1 from MAXVALUES before multiplying by MAXROWS.

// test for exit condition
if (total == (MAXVALUES-1)*MAXROWS)
   status = true; 

We need to replace MAXROWS and MAXVALUES to 3 to make the solution generate the same as the original example.

By changing the value of MAXVALUES we can generate different combinatorics combinations.

Example if we want to generate 0 and and 1s only we can change only

#define MAXVALUES 2

char display[] = {'0','1'}; 

Generalizing Dynamic Loops

Any general calculation can be made in the place the comment given below is.

// We can perform any inner loop calculation here arrs[r] 

In addition we can use if statements to do calculations needed at a specific level of nesting

History

Keep a running update of any changes or improvements you've made here.