Hay alguna forma de hacer n-nivel de bucles anidados en Java?
https://stackoverflow.com/questions/426878
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
En otras palabras, puedo hacer algo como
for() {
for {
for {
}
}
}
Excepto N veces?En otras palabras, cuando el método de creación de los bucles se llama, se le da algún parámetro N, y el método, a continuación, crear N de estos bucles anidados uno en el otro?
Por supuesto, la idea es que no debe ser un "fácil" o "la costumbre" de hacer.Ya tengo una idea para una muy complicado.
Solución
Parece que es posible que desee examinar recursión.
Otros consejos
jjnguy es derecho;la recursividad permite crear dinámicamente variable profundidad de anidamiento.Sin embargo, no podrás tener acceso a los datos de las capas exteriores sin un poco más de trabajo.El "en-línea-anidada" caso:
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**
}
}
}
mantiene las variables i, j, y k en el ámbito de la íntima cuerpo.
He aquí un truco rápido para hacer eso:
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];
}
}
}
}
El IAction interfaz estipula el papel de una acción controlada que lleva a una serie de índices como el argumento para su act método.
En este ejemplo, cada instancia de NestedFor está configurado por el constructor con la iteración de los límites y la acción a realizar por el nivel más profundo.El parámetro de la nFor método especifica la profundidad para anidar.
Aquí se muestra un ejemplo de uso:
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);
}
}
y el (parcial) de la salida de su ejecución:
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
Es posible que desee explicar lo que realmente quiere hacer.
Si los bucles externos for no hacen más que controlar un conteo, entonces sus bucles <=> anidados son simplemente una forma más complicada de iterar mediante un recuento que podría ser manejado por un solo bucle <=>.
Por ejemplo:
for (x = 0; x < 10; ++x) {
for (y = 0; y < 5; ++y) {
for (z = 0; z < 20; ++z) {
DoSomething();
}
}
}
Es equivalente a:
for (x = 0; x < 10*5*20; ++x) {
DoSomething();
}
En realidad estaba pensando en esto el otro día.
Un ejemplo que probablemente no sea perfecto pero que esté bastante cerca de lo que creo que se pregunta sería imprimir un árbol de directorios
public void printTree(directory) {
for(files in directory) {
print(file);
if(file is directory) {
printTree(file);
}
}
}
de esta manera terminas con una pila de bucles for anidados uno dentro del otro, sin la molestia de descubrir exactamente cómo deben ir juntos.
Edición de 2015: a lo largo del mismo vano que el encantamiento anterior, hice el siguiente paquete para manejar esto; https://github.com/BeUndead/NFor
El uso sería el siguiente
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));
}
}
resultando en
[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]
También admite condiciones distintas a lessThan. El uso que existe (con 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));
Resultando en:
[-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]
Obviamente, se admiten bucles de diferentes longitudes y diferentes clases (todos primitivos en caja, numéricos). El valor predeterminado (si no se especifica) es from (0, ...). By (1, ...); pero se debe especificar un a (...).
El archivo NForTest debe mostrar varias formas diferentes de usarlo.
La premisa básica de este ser es simplemente avanzar los 'índices' cada turno en lugar de usar la recursividad.
El problema necesita más especificación. Tal vez la recursión lo ayude, pero tenga en cuenta que la recursión es casi siempre una alternativa a la iteración, y viceversa. Es posible que un bucle anidado de 2 niveles sea suficiente para sus necesidades. Solo díganos qué problema está tratando de resolver.
La idea esencial detrás de anidamiento de bucles es la multiplicación.
Ampliación de Michael Burr respuesta, si el exterior for los bucles están haciendo nada, pero el control de un recuento, su anidados for se repite a lo largo n los recuentos son simplemente una más complicada forma de iterar sobre el producto de los condes con una sola for loop.
Ahora, vamos a extender esta idea a las Listas.Si usted está iterando sobre las tres listas en bucles anidados, esto es simplemente una más complicada forma de iterar sobre el producto de las listas con un solo bucle.Pero ¿cómo expresar el producto de las tres listas?
En primer lugar, necesitamos una manera de expresar el producto de tipos.El producto de dos tipos X y Y puede ser expresado como un tipo genérico como P2<X, Y>.Esto es sólo un valor que consta de dos valores, uno de tipo X, el otro tipo de Y.Se parece a esto:
public abstract class P2<A, B> {
public abstract A _p1();
public abstract B _p2();
}
Para un producto de tres tipos, solo tenemos P3<A, B, C>, con la obvia tercer método.Un producto de tres listas, entonces, se logra mediante la distribución de la Lista functor sobre el tipo de producto.De modo que el producto de List<X>, List<Y>, y List<Z> es simplemente List<P3<X, Y, Z>>.Se puede iterar sobre esta lista con un solo bucle.
El Funcional Java la biblioteca tiene un List tipo compatible con la multiplicación de listas junto con la primera clase de las funciones y tipos de producto (P2, P3, etc.que también están incluidos en la biblioteca).
Por ejemplo:
for (String x : xs) {
for (String y : ys) {
for (String z : zs) {
doSomething(x, y, z);
}
}
}
Es equivalente a:
for (P3<String, String, String> p : xs.map(P.p3()).apply(ys).apply(zs)) {
doSomething(p._1(), p._2(), p._3());
}
Va más Funcional Java, usted puede hacer doSomething de primera clase, de la siguiente manera.Digamos doSomething devuelve una Cadena:
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());
}
};
A continuación, puede eliminar el bucle por completo, y recoger los resultados de todas las aplicaciones de doSomething:
List<String> s = xs.map(P.p3()).apply(ys).apply(zs).map(doSomething);
Si tiene una estructura general de bucle anidado como:
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);
donde i0,i1,i2,...,id son variables de bucle y d es la profundidad del bucle anidado.
Solución de recursión equivalente:
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 es una matriz de tamaño i0,i1,i2,...id, que representa las variables correspondientes int counters[d] respectivamente initial[d], ending[d].
nestedToRecursion(counters,0);
De manera similar, podemos convertir otras variables como la inicialización de la recursión o la finalización utilizando matrices para ellas, es decir, podríamos tener <=>.
El enfoque general más perfecto que se me ocurrió en Java 7 es
// 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] );
}
}
O en 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]; }
);
Una implementación que admite esto es:
/**
* 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();
}
Crea un bonito esqueleto anidado para bucle for ;-) No es completamente serio y soy consciente de que una solución recursiva habría sido más elegante.
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);
}
}
Llamada de muestra:
int[] ranges = {2, 2, 2};
recursiveFor(new ArrayDeque<Integer>(), ranges, ranges.length);
mi primera vez de contestar a una pregunta, pero sentía que necesitaba compartir esta info de `
for (x = 0; x < base; ++x) {
for (y = 0; y < loop; ++y) {
DoSomething();
}
}
es el equivalente a
for (x = 0; x < base*loop; ++x){
DoSomething();
}
así que si usted quería un n número de nidos, puede ser escrito usando la división entre base y loop así que podría ser algo tan simple como esto:
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();
}
}
así que, si el tipo de printer(10, 2); sería impresión:
00
01
02
03
04
...
97
98
99
Esto me funcionó realmente bien: tuve que seleccionar algunas alternativas, que estaban almacenadas en myAlternativePaths y la idea básica es que estaba tratando de construir la siguiente selección, y cuando hubo un " ¡desbordamiento quot; en una dimensión / componente, simplemente reinicializa esa dimensión y agrega una a la siguiente.
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;
}
En aras de la concisión, pongo mi código aquí:
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);
}
Salida
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
