Existe-t-il un moyen de créer des boucles imbriquées de niveau n en Java?
https://stackoverflow.com/questions/426878
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
En d'autres termes, puis-je faire quelque chose comme
for() {
for {
for {
}
}
}
Sauf N fois? En d’autres termes, lorsqu’on appelle la méthode qui crée les boucles, on lui donne un paramètre N et la méthode créerait alors N de ces boucles imbriquées les unes dans les autres?
Bien sûr, l’idée est qu’il devrait y avoir un & "easy &"; ou & "l'habituel &"; façon de le faire. J'ai déjà une idée très compliquée.
La solution
Il semble que vous souhaitiez peut-être examiner la récursivité.
Autres conseils
jjnguy a raison; la récursivité vous permet de créer dynamiquement des imbrications à profondeur variable. Cependant, vous n’avez pas accès aux données des couches externes sans un peu plus de travail. Le & "; Imbriqué en ligne &"; cas:
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**
}
}
}
conserve les variables i, j et k à la portée du corps le plus à l'intérieur à utiliser.
Voici un petit hack pour le faire:
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];
}
}
}
}
L'interface IAction stipule le rôle d'une action contrôlée qui prend un tableau d'indices comme argument de sa méthode act.
Dans cet exemple, chaque instance de NestedFor est configurée par le constructeur avec les limites d'itération et l'action à exécuter par le niveau le plus à l'intérieur. Le paramètre de la méthode nFor spécifie la profondeur d'imbrication.
Voici un exemple d'utilisation:
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);
}
}
et la sortie (partielle) de son exécution:
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
Vous voudrez peut-être expliquer ce que vous voulez vraiment faire.
Si les boucles for extérieures ne font que contrôler un compte, vos boucles <=> imbriquées constituent simplement un moyen plus compliqué d'itérer un compte pouvant être géré par une seule <=> boucle.
Par exemple:
for (x = 0; x < 10; ++x) {
for (y = 0; y < 5; ++y) {
for (z = 0; z < 20; ++z) {
DoSomething();
}
}
}
est équivalent à:
for (x = 0; x < 10*5*20; ++x) {
DoSomething();
}
J'y pensais en fait l'autre jour.
Un exemple qui n’est probablement pas parfait, mais qui est assez proche de ce que je pense que l’on demande, serait d’imprimer une arborescence de répertoires
public void printTree(directory) {
for(files in directory) {
print(file);
if(file is directory) {
printTree(file);
}
}
}
De cette façon, vous vous retrouvez avec une pile de boucles for imbriquées les unes dans les autres, sans la peine de déterminer exactement comment elles doivent aller ensemble.
Édition 2015: Parallèlement à l'incantation précédente, j'ai créé le package suivant pour gérer cela; https://github.com/BeUndead/NFor
L'utilisation serait la suivante
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));
}
}
ayant pour résultat
[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]
Il prend également en charge des conditions autres que lessThan. L’utilisation qui existe (avec 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));
Résultat:
[-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]
Bien entendu, les boucles de différentes longueurs et de différentes classes (toutes les primitives numériques encadrées) sont prises en charge. La valeur par défaut (si non spécifié) est from (0, ...). By (1, ...); mais il faut spécifier a (...).
Le fichier NForTest doit présenter différentes manières de l'utiliser.
Le principe de base de ceci est simplement de faire avancer les "indices" à chaque tour plutôt que d'utiliser la récursivité.
Le problème nécessite plus de précisions. Peut-être que la récursivité vous aidera, mais gardez à l'esprit que la récursion est presque toujours une alternative à l'itération, et inversement. Il se peut qu'une boucle imbriquée à 2 niveaux puisse suffire à vos besoins. Dites-nous simplement quel problème vous essayez de résoudre.
L'idée essentielle derrière les boucles imbriquées est la multiplication .
Répondant à la réponse de Michael Burr, si les boucles for extérieures ne font que contrôler un compte, alors vos boucles n imbriquées sur X les compteurs sont simplement un moyen plus compliqué d’itérer le produit des comptages. avec une seule Y boucle.
Maintenant, étendons cette idée aux listes. Si vous parcourez trois listes dans des boucles imbriquées, il s'agit simplement d'un moyen plus compliqué de parcourir le produit des listes avec une seule boucle. Mais comment exprimez-vous le produit de trois listes?
Premièrement, nous avons besoin d’un moyen d’exprimer le produit des types. Le produit de deux types P2<X, Y> et P3<A, B, C> peut être exprimé sous forme d'un type générique tel que List<X>. Il s’agit simplement d’une valeur composée de deux valeurs, l’une de type List<Y>, l’autre de type List<Z>. Cela ressemble à ceci:
public abstract class P2<A, B> {
public abstract A _p1();
public abstract B _p2();
}
Pour un produit de trois types, nous avons juste List<P3<X, Y, Z>>, avec la troisième méthode évidente. On obtient alors un produit de trois listes en répartissant le foncteur Liste sur le type de produit. Le produit de List, doSomething et <=> est donc simplement <=>. Vous pouvez ensuite parcourir cette liste avec une seule boucle.
La bibliothèque Java fonctionnel a un type <=> qui prend en charge la multiplication de listes en utilisant des fonctions et des types de produits de première classe. (P2, P3, etc., qui sont également inclus dans la bibliothèque).
Par exemple:
for (String x : xs) {
for (String y : ys) {
for (String z : zs) {
doSomething(x, y, z);
}
}
}
est équivalent à:
for (P3<String, String, String> p : xs.map(P.p3()).apply(ys).apply(zs)) {
doSomething(p._1(), p._2(), p._3());
}
Pour aller plus loin avec Java fonctionnel, vous pouvez définir <=> de première classe, comme suit. Disons que <=> retourne une chaîne:
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());
}
};
Ensuite, vous pouvez éliminer complètement la boucle for, et collecter les résultats de toutes les applications de <=>:
List<String> s = xs.map(P.p3()).apply(ys).apply(zs).map(doSomething);
Si vous rencontrez une structure de boucle imbriquée générale telle que:
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);
où i0,i1,i2,...,id sont des variables de boucle et d la profondeur de la boucle imbriquée.
Solution de récursivité équivalente:
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 est un tableau de taille i0,i1,i2,...id, représentant les variables correspondantes int counters[d] respectivement initial[d], ending[d].
nestedToRecursion(counters,0);
De même, nous pouvons convertir d'autres variables telles que l'initialisation de la récursion ou la fin en utilisant des tableaux pour celles-ci, c'est-à-dire que nous pourrions avoir <=>.
La meilleure approche générale que je pourrais trouver dans Java 7 est
// 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] );
}
}
Ou 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]; }
);
Une implémentation prenant en charge cette fonctionnalité est la suivante:
/**
* 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();
}
Crée un joli squelette imbriqué pour la boucle ;-) Pas tout à fait sérieux et je suis conscient qu'une solution récursive aurait été plus élégante.
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);
}
}
Exemple d'appel:
int[] ranges = {2, 2, 2};
recursiveFor(new ArrayDeque<Integer>(), ranges, ranges.length);
la première fois que je répondais à une question mais je sentais que je devais partager cette information de `
for (x = 0; x < base; ++x) {
for (y = 0; y < loop; ++y) {
DoSomething();
}
}
étant équivalent à
for (x = 0; x < base*loop; ++x){
DoSomething();
}
donc si vous voulez un nombre n de nids, vous pouvez l'écrire en utilisant une division entre base et loop, de sorte que le résultat soit aussi simple que cela:
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();
}
}
donc si vous deviez taper printer(10, 2);, cela afficherait:
00
01
02
03
04
...
97
98
99
Cela a fonctionné pour moi vraiment bien - je devais choisir parmi quelques alternatives, qui étaient stockées dans myAlternativePaths et l'idée de base est que j'essayais de construire la sélection suivante, et quand il y avait un & "; débordement quot; dans une dimension / composant, il vous suffit de réinitialiser cette dimension et d’en ajouter une à la suivante.
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;
}
Dans un souci de concision, je mets mon code ici:
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);
}
Sortie
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
