Dynamically change the number of nested for loops

Question

I don't know if this is a stupid question, but I need to dynamically change the number of for-loops without using recursion.

For example, if n=3, I need 3 nested for-loops.

for(int i=0; i<size; i++){
   for(int j=0; j<size-1; j++){
       for(int k=0; k<size-2; k++){
          //do something
       }
   }
}

If n=5:

for(int i=0; i<size; i++){
   for(int j=0; j<size-1; j++){
       for(int k=0; k<size-2; k++){
          for(int l=0; l<size-3; l++){
              for(int m=0; m<size-4; m++){
                  //do something
              }
          }
       }
   }
}

Is there any way to achieve this without recursion? Another question: what is the use of Multiple Dispatch in Java? I'm trying to code something in ONE METHOD, and it should run different events in different cases of the parameter. NO IF STATEMENTS / TERNARY OPERATORS / CASES.

NOTE: I can ONLY have one method (part of the problem), and cannot use recursion. Sorry.

Precisely what are the inputs and outputs? I'm afraid the answer is probably dependent on them. — Ed Staub, Nov 27 '13 at 19:05
It can't be positive infinity on a computer. It can be `Integer.MAX_VALUE` or `Long.MAX_VALUE`. There is a way to make it larger but `Long.MAX_VALUE` is arbitrarily large enough that looping for `0...Long.MAX_VALUE` could take years to complete. — Radiodef, Nov 27 '13 at 19:15
What if you explained the whole problem? Maybe you're focusing on the wrong way to solve the ground problem. — Thibault D., Nov 27 '13 at 19:21
I have to agree with @thibaultd that you haven't totally explained your use-case here. You have a variable `size` that it looks like you want to involve. The other important point is whether you want to do something in any of the loops except the most-inner one. Otherwise it seems like your question has been answered. — Radiodef, Nov 27 '13 at 20:53
Yes, I want to do something in each of the loops. This is actually for outputting an equation to n by n matrix determinant using CodeModel. I'm restricted to using only one method thus I cannot use recursion. The only way I thought of is dynamic nested for loops. Thanks for the informative answers otherwise. — Stevantti, Nov 27 '13 at 23:26
The inputs are an array of strings that represent an n by n matrix and the size of the matrix. It is to output an equation in string that calculates the determinant. — Stevantti, Nov 27 '13 at 23:29
You only need one while loop to do that... And an array of n indexes. — Thibault D., Nov 28 '13 at 17:37
Explain your problem first clearly, as I don't fully understand it. My solution would require some IFs but you say you can't have them, how so? Every for loop you produce contains itself an IF (m — Thibault D., Nov 29 '13 at 14:48

score 3 · Accepted Answer · answered Nov 27 '13 at 19:17

3

Think about how many times you run through this loop. It looks like (size!) / (size - n)!:

int numLoops = 1;
for (int i = 0; i < n; i++) {
    numLoops*= (size - i);
}

for (int i = 0; i < numLoops; i++) {
    //do something
}

answered Nov 27 '13 at 19:17

quazzieclodo

831
4
10

score 1 · Answer 2 · edited May 23 '17 at 11:45

1

It depends what exactly you're trying to do. Recursion can always be replaced with iteration (see this post for examples using a Stack to store state).

But perhaps the modulo (%) operator could work here? i.e. Have a single loop that increments a variable (i) and then the other variables are calculated using modulo (i % 3 etc). You could use a Map to store the values of the variables indirectly, if there are a varying number of variables.

edited May 23 '17 at 11:45

Community

1
1

answered Nov 27 '13 at 19:08

ᴇʟᴇvᴀтᴇ

12,285
4
43
66

Sure, yes, that's a known fact. So even better. He can use my idea and replace the recursion with Stack if the levels of nesting are too many. I doubt the modulo would help. I think he just wants to code N nested loops but that N being a variable. – peter.petrov Nov 27 '13 at 19:11

score 1 · Answer 3 · answered Nov 27 '13 at 20:11

You have to create array of loop counters and increment it manually.

Quick and dirty example:

public static void nestedFors(int n, int size) {
  assert n > size;
  assert size > 0;

  int[] i = new int[n];
  int l = n - 1;
  while(l >= 0) {
    if(l == n - 1) {
      System.out.println(Arrays.toString(i));
    }
    i[l]++;
    if(i[l] == size - l) {
      i[l] = 0;
      l--;
    } else if(l < n - 1) {
      l++;
    }
  }
}

Replace System.out.println(Arrays.toString(i)) with your own code.

You can check it here: http://ideone.com/IKbDUV

If the OP wants to do something with `n` counters I don't see a way around doing something like this. — Radiodef, Nov 27 '13 at 20:41

peter.petrov · Answer 4 · 2014-01-07T22:25:49.270

I think you need a backtracking algorithm. But then you would replace your nested loops with recursion.

I don't want to post links here as seems moderators don't like that.

Look at "eight queens puzzle" (you can Google it), you will get my idea.

I know this idea works as I've posed this same question (which you have) to myself on many occasions, and I've applied it several times successfully.

Here is a small example (I changed it as the previous one was a bit complex).

public class Test001 {

public static void main(String[] args) {
    loop(0, 5, 10);
}

/**
 * max_level - the max count of nesting loops
 * size - the size of the collection
 * 
 * 0 - top most level
 * level 1 - nested into 0
 * level 2 - nested into 1
 * ... 
 * and so on.
 */
private static void loop(int level, int max_level, int size){
    if (level > max_level) return;

    for (int i=0; i<size-level; i++){
        System.out.println("Now at level: " + level + " counter = " + i);
        loop(level + 1, max_level, size);
    }
}

}

But this still uses recursion.

No they don't (don't like that) ;). Citing references is good. It just shouldn't be a link only answer though. — mtk, Nov 27 '13 at 19:04

ljgw · Answer 5 · 2013-11-27T21:30:05.683

It's a bit convoluted, but: here is a way to do it without recursion, in one function and without ifs.

public static void no_ifs_no_recursion(int n){  
    int[] helper = new int[n-1];
    int[] pointers = new int[n]; //helper for printing the results

    int totalsize = 1;
    for (int loops = 2; loops <= n; loops++){
        helper[n - loops] = totalsize;
        totalsize*=loops;
    }
    for (int i=0; i<totalsize; i++){
        int carry = i;
        for (int loops = 0; loops < n-1; loops++){
            pointers[loops] = carry/helper[loops];
            carry = carry - (pointers[loops]*helper[loops]);
        }

        System.out.println(Arrays.toString(pointers));
        //or do something else with `i` -> `pointers[0]`, `j` -> `pointers[1]`, `k` -> `pointers[2]` etc..
    }
}

Dynamically change the number of nested for loops

5 Answers5

Linked