14,550,658 members

# Generating dynamically nested loops

Rate this:
15 Apr 2014CPOL
One example of the need to have a set of nested loops in is combinotronics where you are trying to generate all possible combinations. If we want to have a variable number of elements generated then we need to look at having 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

The code below generates all possible values of 1,2,3
```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.

## Share

 New Zealand
NATKIT loves programming and currently working with C/C++. He is interested in working on designing and implementing various algorithms. He is looking into the development of algorithms that leverage on the parallel hardware that is readily available such as Mutli Core Processors, GP-GPU and Distributed Parallelism using MPI

 First Prev Next
 My vote of 3 Peter Bingham21-Apr-14 4:25 Peter Bingham 21-Apr-14 4:25
 Re: My vote of 3 Peter Bingham21-Apr-14 4:53 Peter Bingham 21-Apr-14 4:53
 Last Visit: 6-Jun-20 4:12     Last Update: 6-Jun-20 4:12 Refresh 1