Is there any way to do n-level nested loops in Java?
https://stackoverflow.com/questions/426878
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
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
It sounds like you may want to look into recursion.
OTHER TIPS
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
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();
}
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.
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.
Problem needs more specification. Maybe recursion will help you, but keep in mind that recursion is almost always an alternative to iteration, and vice versa. It may be that a 2-level nested loop can be sufficient for your needs. Just let us know what problem you're trying to solve.
The essential idea behind nesting loops is multiplication.
Expanding on Michael Burr's answer, if the outer for loops are doing nothing but controlling a count, then your nested for loops over n counts are simply a more complicated way of iterating over the product of the counts with a single for loop.
Now, let's extend this idea to Lists. If you're iterating over three lists in nested loops, this is simply a more complicated way of iterating over the product of the lists with a single loop. But how do you express the product of three lists?
First, we need a way of expressing the product of types. The product of two types X and Y can be expressed as a generic type like P2<X, Y>. This is just a value that consists of two values, one of type X, the other of type Y. It looks like this:
public abstract class P2<A, B> {
public abstract A _p1();
public abstract B _p2();
}
For a product of three types, we just have P3<A, B, C>, with the obvious third method. A product of three lists, then, is achieved by distributing the List functor over the product type. So the product of List<X>, List<Y>, and List<Z> is simply List<P3<X, Y, Z>>. You can then iterate over this list with a single loop.
The Functional Java library has a List type that supports multiplying lists together using first-class functions and product types (P2, P3, etc. which are also included in the library).
For example:
for (String x : xs) {
for (String y : ys) {
for (String z : zs) {
doSomething(x, y, z);
}
}
}
Is equivalent to:
for (P3<String, String, String> p : xs.map(P.p3()).apply(ys).apply(zs)) {
doSomething(p._1(), p._2(), p._3());
}
Going further with Functional Java, you can make doSomething first-class, as follows. Let's say doSomething returns a String:
public static final F<P3<String, String, String>, String> doSomething =
new F<P3<String, String, String>, String>() {
public String f(final P3<String, String, String> p) {
return doSomething(p._1(), p._2(), p._3());
}
};
Then you can eliminate the for-loop altogether, and collect the results of all the applications of doSomething:
List<String> s = xs.map(P.p3()).apply(ys).apply(zs).map(doSomething);
If you are having a general nested-loop structure like:
for(i0=0;i0<10;i0++)
for(i1=0;i1<10;i1++)
for(i2=0;i2<10;i2++)
....
for(id=0;id<10;id++)
printf("%d%d%d...%d\n",i0,i1,i2,...id);
where i0,i1,i2,...,id are loop variables and d is the depth of the nested loop.
Equivalent Recursion Solution:
void nestedToRecursion(counters,level){
if(level == d)
computeOperation(counters,level);
else
{
for (counters[level]=0;counters[level]<10;counters[level]++)
nestedToRecursion(counters,level+1);
}
}
void computeOperation(counters,level){
for (i=0;i<level;i++)
printf("%d",counters[i]);
printf("\n");
}
counters is an array of size d, representing the corresponding variables i0,i1,i2,...id respectively int counters[d].
nestedToRecursion(counters,0);
Similarly we can convert other variables like initializing of recursion or ending by using arrays for them, i.e. we could have initial[d], ending[d].
The neatest general approach I could come up with in Java 7 is
// i[0] = 0..1 i[1]=0..3, i[2]=0..4
MultiForLoop.loop( new int[]{2,4,5}, new MultiForLoop.Callback() {
void act(int[] i) {
System.err.printf("%d %d %d\n", i[0], i[1], i[2] );
}
}
Or in Java 8:
// i[0] = 0..1 i[1]=0..3, i[2]=0..4
MultiForLoop.loop( new int[]{2,4,5},
i -> { System.err.printf("%d %d %d\n", i[0], i[1], i[2]; }
);
An implementation that supports this is:
/**
* Uses recursion to perform for-like loop.
*
* Usage is
*
* MultiForLoop.loop( new int[]{2,4,5}, new MultiForLoop.Callback() {
* void act(int[] indices) {
* System.err.printf("%d %d %d\n", indices[0], indices[1], indices[2] );
* }
* }
*
* It only does 0 - (n-1) in each direction, no step or start
* options, though they could be added relatively trivially.
*/
public class MultiForLoop {
public static interface Callback {
void act(int[] indices);
}
static void loop(int[] ns, Callback cb) {
int[] cur = new int[ns.length];
loop(ns, cb, 0, cur);
}
private static void loop(int[] ns, Callback cb, int depth, int[] cur) {
if(depth==ns.length) {
cb.act(cur);
return;
}
for(int j = 0; j<ns[depth] ; ++j ) {
cur[depth]=j;
loop(ns,cb, depth+1, cur);
}
}
}
String fors(int n){
StringBuilder bldr = new StringBuilder();
for(int i = 0; i < n; i++){
for(int j = 0; j < i; j++){
bldr.append('\t');
}
bldr.append("for() {\n");
}
for(int i = n-1; i >= 0; i--){
for(int j = 0; j < i; j++){
bldr.append('\t');
}
bldr.append("}\n");
}
return bldr.toString();
}
Creates a nice nested for-loop skeleton ;-) Not completely serious and i'm aware that a recursive solution would have been more elegant.
public void recursiveFor(Deque<Integer> indices, int[] ranges, int n) {
if (n != 0) {
for (int i = 0; i < ranges[n-1]; i++) {
indices.push(i);
recursiveFor(indices, ranges, n-1);
indices.pop();
}
}
else {
// inner most loop body, access to the index values thru indices
System.out.println(indices);
}
}
Sample call:
int[] ranges = {2, 2, 2};
recursiveFor(new ArrayDeque<Integer>(), ranges, ranges.length);
my first time answering a question but i felt like i needed to share this info of `
for (x = 0; x < base; ++x) {
for (y = 0; y < loop; ++y) {
DoSomething();
}
}
being equivalent to
for (x = 0; x < base*loop; ++x){
DoSomething();
}
so if you wanted an n number of nests, it can be written using division between base and loop so it could look something as simple as this:
char[] numbs = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
public void printer(int base, int loop){
for (int i = 0; i < pow(base, loop); i++){
int remain = i;
for (int j = loop-1; j >= 0; j--){
int digit = remain/int(pow(base, j));
print(numbs[digit]);
remain -= digit*pow(base, j);
}
println();
}
}
so if you were to type printer(10, 2); it would print out:
00
01
02
03
04
...
97
98
99
This worked for me really nice - I had to select from some alternatives, which were stored in myAlternativePaths and the basic idea is that I was trying to construct next selection, and when there was an "overflow" in one dimension / component, you just reinitialize that dimension and add one to the next.
public boolean isValidAlternativeSelection (int[] alternativesSelected) {
boolean allOK = true;
int nPaths= myAlternativePaths.size();
for (int i=0; i<nPaths; i++) {
allOK=allOK & (alternativesSelected[i]<myAlternativePaths.get(i).myAlternativeRoutes.size());
}
return allOK;
}
public boolean getNextValidAlternativeSelection (int[] alternativesSelected) {
boolean allOK = true;
int nPaths= myAlternativePaths.size();
alternativesSelected[0]=alternativesSelected[0]+1;
for (int i=0; i<nPaths; i++) {
if (alternativesSelected[i]>=myAlternativePaths.get(i).myAlternativeRoutes.size()) {
alternativesSelected[i]=0;
if(i<nPaths-1) {
alternativesSelected[i+1]=alternativesSelected[i+1]+1;
} else {
allOK = false;
}
}
// allOK=allOK & (alternativesSelected[i]<myAlternativePaths.get(i).myAlternativeRoutes.size());
}
return allOK;
}
In the interest of conciseness I am putting my code here :
void variDepth(int depth, int n, int i) {
cout<<"\n d = "<<depth<<" i = "<<i;
if(!--depth) return;
for(int i = 0;i<n;++i){
variDepth(depth,n,i);
}
}
void testVariDeapth()
{ variDeapth(3, 2,0);
}
Output
d = 3 i = 0
d = 2 i = 0
d = 1 i = 0
d = 1 i = 1
d = 2 i = 1
d = 1 i = 0
d = 1 i = 1
