Is there any way to do n-level nested loops in Java?

Question

In other words, can I do something like

for() {
    for {
       for {
       }
    }
}

Except N times? In other words, when the method creating the loops is called, it is given some parameter N, and the method would then create N of these loops nested one in another?

Of course, the idea is that there should be an "easy" or "the usual" way of doing it. I already have an idea for a very complicated one.

Solution 1

It sounds like you may want to look into recursion.

Solution 2

jjnguy is right; recursion lets you dynamically create variable-depth nesting. However, you don't get access to data from the outer layers without a little more work. The "in-line-nested" case:

for (int i = lo; i < hi; ++i) {
    for (int j = lo; j < hi; ++j) {
        for (int k = lo; k < hi; ++k) {
            // do something **using i, j, and k**
        }
    }
}

keeps the variables i, j, and k in scope for the innermost body to use.

Here's one quick hack to do that:

public class NestedFor {

    public static interface IAction {
        public void act(int[] indices);
    }

    private final int lo;
    private final int hi;
    private final IAction action;

    public NestedFor(int lo, int hi, IAction action) {
        this.lo = lo;
        this.hi = hi;
        this.action = action;
    }

    public void nFor (int depth) {
        n_for (0, new int[0], depth);
    }

    private void n_for (int level, int[] indices, int maxLevel) {
        if (level == maxLevel) {
            action.act(indices);
        } else {
            int newLevel = level + 1;
            int[] newIndices = new int[newLevel];
            System.arraycopy(indices, 0, newIndices, 0, level);
            newIndices[level] = lo;
            while (newIndices[level] < hi) {
                n_for(newLevel, newIndices, maxLevel);
                ++newIndices[level];
            }
        }
    }
}

The IAction interface stipulates the role of a controlled action which takes an array of indices as the argument to its act method.

In this example, each instance of NestedFor is configured by the constructor with the iteration limits and the action to be performed by the innermost level. The parameter of the nFor method specifies how deeply to nest.

Here's a sample usage:

public static void main(String[] args) {
    for (int i = 0; i < 4; ++i) {
        final int depth = i;
        System.out.println("Depth " + depth);
        IAction testAction = new IAction() {
            public void act(int[] indices) {
                System.out.print("Hello from level " + depth + ":");
                for (int i : indices) { System.out.print(" " + i); }
                System.out.println();
            }
        };
        NestedFor nf = new NestedFor(0, 3, testAction);
        nf.nFor(depth);
    }
}

and the (partial) output from its execution:

Depth 0
Hello from level 0:
Depth 1
Hello from level 1: 0
Hello from level 1: 1
Hello from level 1: 2
Depth 2
Hello from level 2: 0 0
Hello from level 2: 0 1
Hello from level 2: 0 2
Hello from level 2: 1 0
Hello from level 2: 1 1
Hello from level 2: 1 2
Hello from level 2: 2 0
Hello from level 2: 2 1
Hello from level 2: 2 2
Depth 3
Hello from level 3: 0 0 0
Hello from level 3: 0 0 1
Hello from level 3: 0 0 2
Hello from level 3: 0 1 0
...
Hello from level 3: 2 1 2
Hello from level 3: 2 2 0
Hello from level 3: 2 2 1
Hello from level 3: 2 2 2

Solution 3

2015 Edit: Along the same vain as the previous incantation, I made the following package to handle this; https://github.com/BeUndead/NFor

The usage would be as follows

public static void main(String... args) {
    NFor<Integer> nfor = NFor.of(Integer.class)
            .from(0, 0, 0)
            .by(1, 1, 1)
            .to(2, 2, 3);

    for (Integer[] indices : nfor) {
        System.out.println(java.util.Arrays.toString(indices));
    }
}

resulting in

[0, 0, 0]
[0, 0, 1]
[0, 0, 2]
[0, 1, 0]
[0, 1, 1]
[0, 1, 2]
[1, 0, 0]
[1, 0, 1]
[1, 0, 2]
[1, 1, 0]
[1, 1, 1]
[1, 1, 2]

It also supports conditions other than lessThan. The usage there being (with import static NFor.*;):

NFor<Integer> nfor = NFor.of(Integer.class)
        .from(-1, 3, 2)
        .by(1, -2, -1)
        .to(lessThanOrEqualTo(1), greaterThanOrEqualTo(-1), notEqualTo(0));

Resulting in:

[-1, 3, 2]
[-1, 3, 1]
[-1, 1, 2]
[-1, 1, 1]
[-1, -1, 2]
[-1, -1, 1]
[0, 3, 2]
[0, 3, 1]
[0, 1, 2]
[0, 1, 1]
[0, -1, 2]
[0, -1, 1]
[1, 3, 2]
[1, 3, 1]
[1, 1, 2]
[1, 1, 1]
[1, -1, 2]
[1, -1, 1]

Obviously, loops of different lengths and different classes (all boxed, numeric primitives) are supported. The default (if not specified) is from(0, ...).by(1, ...); but a to(...) must be specified.

The NForTest file should demonstrate several different ways to use it.

The basic premise of this being to simply advance the 'indices' each turn rather than use recursion.

Solution 4

I was actually thinking about this the other day.

An example that is probably not perfect but pretty close to what I think is being asked would be printing out a directory tree

public void printTree(directory) {
   for(files in directory) {
      print(file);
      if(file is directory) {
          printTree(file);
      }
   }
}

this way you end up with a stack of for loops nested inside each other, without the hassle of figuring out exactly how they should go together.

Solution 5

You might want to explain what you really want to do.

If the outer for loops are doing nothing but controlling a count, then your nested for loops are simply a more complicated way of iterating by a count that could be handled by a single for loop.

For example:

for (x = 0; x < 10; ++x) {
  for (y = 0; y < 5; ++y) {
    for (z = 0; z < 20; ++z) {
      DoSomething();
    }
  }
}

Is equivalent to:

for (x = 0; x < 10*5*20; ++x) {
  DoSomething();
}

View more solutions

Comments

[Apocalisp]

Good answer. This captures the essence of nesting loops. See my answer for a generalization of this idea.

[Apocalisp]

This still does not answer the question. For-iteration IS a kind of recursion. Perhaps you intend to include an example of mutual recursion?

[Rolf Rander]

This is a typical use for recursion, where you are traversing a recursive datastructure.

[Michael Kutschke]

no, i'm just saying the question is not clear. The whole issue could also be something like "how do i get my IDE to give me a n-level for-loop template". My code is pretty far away from generating code at runtime, it was meant as code-generation at development-time, aka templates. Btw. the author has not once said he wanted to execute the loops right away. I am just interpreting the question a little different than the other people who answered it before me.

[Ajeet Ganga]

You can always generate a perl file from java code and then execute it. :) And we are totally serious about doing so. :)

[liang]

Great answer. I prefer this one over recursion

[Pacerier]

Isn't this actually employing recursion as well internally?

[joel.neely]

@Pacerier, yes, the explicit recursion occurs in the private n_for method on the NestedFor class. (I would write this differently in Java 8, of course :)

[Michael Anderson]

This is a great approach, I'd wrap it in a nice class and provide a callback to make it neater...

[patapouf_ai]

What is this IAction class you are using? I cannot find what I should import to use it...

[user1048917]

It's not a separate class, it's an interface that joel.neely defines at the top. Then whatever you want to do at the end of the for loop, you would have to write a separate class that implements IAction and has something in act(int[] indices).

[joel.neely]

I appreciate the connection with multiplication, but it seems to break down if we move away from "bounds" known prior the outer level. If one has e.g. for (shelf : library) {for (book : shelf) {for (page : book) {...}}} that has a different "shape" than the one resulting from xs, ys, and zs being established outside the entire construct.

[Apocalisp]

@joel.neely That is totally true, and you've articulated the difference between applicative functors (used in this answer) and monads.

[konnovdev]

This should be the accepted answer