Click here to Skip to main content
11,438,226 members (68,902 online)
Click here to Skip to main content

Generating dynamically nested loops

, 15 Apr 2014 CPOL
Rate this:
Please Sign up or sign in to vote.
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.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

NATKIT7

New Zealand 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

Comments and Discussions

 
GeneralMy vote of 3 Pin
Peter Bingham21-Apr-14 5:25
memberPeter Bingham21-Apr-14 5:25 
GeneralRe: My vote of 3 Pin
Peter Bingham21-Apr-14 5:53
memberPeter Bingham21-Apr-14 5:53 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web04 | 2.8.150506.1 | Last Updated 15 Apr 2014
Article Copyright 2014 by NATKIT7
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid