Existe alguma maneira de fazer n-nível de loops aninhados em Java?
https://stackoverflow.com/questions/426878
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Em outras palavras, pode-se fazer algo como
for() {
for {
for {
}
}
}
Exceto N vezes?Em outras palavras, quando o método de criação de loops é chamado, é dado algum parâmetro N, e o método de faria N destes loops aninhados um no outro?
Claro, a idéia é a de que deve haver um "fácil" ou "habitual" maneira de fazê-lo.Eu já tenho uma ideia para um muito complicada.
Solução
Parece que você pode querer olhar para recursão.
Outras dicas
Jjnguy está certo; A recursão permite criar dinamicamente o ninho de profundidade variável. No entanto, você não obtém acesso a dados das camadas externas sem um pouco mais de trabalho. O caso "em linha aninhada":
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**
}
}
}
Mantém as variáveis i, j, e k em escopo para o corpo mais íntimo usar.
Aqui está um truque rápido para fazer isso:
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];
}
}
}
}
o IAction A interface estipula o papel de uma ação controlada que leva uma variedade de índices como argumento para seu act método.
Neste exemplo, cada instância de NestedFor é configurado pelo construtor com os limites de iteração e a ação a ser executada pelo nível mais interno. O parâmetro do nFor O método especifica o quão profundamente aninhar.
Aqui está um uso de amostra:
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);
}
}
e a saída (parcial) de sua execução:
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
Você pode querer explicar o que realmente deseja fazer.
Se o exterior for Loops não estão fazendo nada além de controlar uma contagem, depois seu aninhado for Loops são simplesmente uma maneira mais complicada de iterando por uma contagem que poderia ser tratada por um único for ciclo.
Por exemplo:
for (x = 0; x < 10; ++x) {
for (y = 0; y < 5; ++y) {
for (z = 0; z < 20; ++z) {
DoSomething();
}
}
}
É equivalente a:
for (x = 0; x < 10*5*20; ++x) {
DoSomething();
}
Na verdade, eu estava pensando nisso outro dia.
Um exemplo que provavelmente não é perfeito, mas bem perto do que acho que está sendo solicitado, estaria imprimindo uma árvore de diretório
public void printTree(directory) {
for(files in directory) {
print(file);
if(file is directory) {
printTree(file);
}
}
}
Dessa forma, você acaba com uma pilha de loops aninhados dentro um do outro, sem o incômodo de descobrir exatamente como eles devem ir juntos.
Editar 2015: Ao longo da mesma vaidade do encantamento anterior, fiz o seguinte pacote para lidar com isso; https://github.com/beundead/nfor
O uso seria o seguinte
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 em
[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]
Também suporta condições que não sejam lessThan. O uso existe (com 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 em:
[-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, loops de diferentes comprimentos e diferentes classes (todas as primitivas numéricas e em caixa) são suportadas. O padrão (se não especificado) é de (0, ...). Por (1, ...); mas a a (...) deve ser especificado.
o NForTest O arquivo deve demonstrar várias maneiras diferentes de usá -lo.
A premissa básica deste ser para simplesmente avançar os 'índices' a cada turno, em vez de usar a recursão.
Problema precisa de mais especificações. Talvez a recursão o ajude, mas lembre -se de que a recursão é quase sempre uma alternativa à iteração e vice -versa. Pode ser que um loop aninhado de dois níveis possa ser suficiente para suas necessidades. Deixe -nos saber que problema você está tentando resolver.
A idéia essencial por trás dos loops de ninho é multiplicação.
Expandindo a resposta de Michael Burr, se o exterior for Loops não estão fazendo nada além de controlar uma contagem, depois seu aninhado for loops acabaram n As contagens são simplesmente uma maneira mais complicada de iterando sobre o produto da contagem com um único for ciclo.
Agora, vamos estender essa ideia a listas. Se você está iterando mais de três listas em loops aninhados, essa é simplesmente uma maneira mais complicada de iterar o produto das listas com um único loop. Mas como você expressa o produto de três listas?
Primeiro, precisamos de uma maneira de expressar o produto de tipos. O produto de dois tipos X e Y pode ser expresso como um tipo genérico como P2<X, Y>. Este é apenas um valor que consiste em dois valores, um do tipo X, o outro do tipo Y. Se parece com isso:
public abstract class P2<A, B> {
public abstract A _p1();
public abstract B _p2();
}
Para um produto de três tipos, apenas temos P3<A, B, C>, com o terceiro método óbvio. Um produto de três listas, então, é alcançado distribuindo o functor da lista pelo tipo de produto. Então, o produto de List<X>, List<Y>, e List<Z> e simples List<P3<X, Y, Z>>. Você pode iterar sobre esta lista com um único loop.
o Java funcional A biblioteca tem um List Tipo que suporta listas multiplicando usando funções e tipos de produtos de primeira classe (P2, P3, etc., que também estão incluídos na biblioteca).
Por exemplo:
for (String x : xs) {
for (String y : ys) {
for (String z : zs) {
doSomething(x, y, z);
}
}
}
É equivalente a:
for (P3<String, String, String> p : xs.map(P.p3()).apply(ys).apply(zs)) {
doSomething(p._1(), p._2(), p._3());
}
Indo além com Java funcional, você pode fazer doSomething Primeira classe, como segue. Digamos doSomething Retorna uma 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());
}
};
Então você pode eliminar completamente o loop e coletar os resultados de todas as aplicações de doSomething:
List<String> s = xs.map(P.p3()).apply(ys).apply(zs).map(doSomething);
Se você está tendo um general nested-loop-estrutura 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);
onde i0,i1,i2,...,id são variáveis de loop e d a profundidade do loop aninhado.
Equivalente A Recursividade Solução:
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");
}
contadores é uma matriz de tamanho d, que representam as variáveis correspondentes i0,i1,i2,...id respectivamente int counters[d].
nestedToRecursion(counters,0);
Da mesma forma podemos converter outras variáveis como a inicialização de recursão final ou através da utilização de matrizes para eles, i.é.poderíamos ter initial[d], ending[d].
A abordagem geral mais interessante que eu poderia encontrar no Java 7 é
// 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 em 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]; }
);
Uma implementação que apóia isso é:
/**
* 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();
}
Cria um bom esqueleto aninhado para o loop ;-) Não é completamente sério e estou ciente de que uma solução recursiva teria sido mais 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);
}
}
Chamado de amostra:
int[] ranges = {2, 2, 2};
recursiveFor(new ArrayDeque<Integer>(), ranges, ranges.length);
Minha primeira vez respondendo a uma pergunta, mas senti que precisava compartilhar essas informações de `
for (x = 0; x < base; ++x) {
for (y = 0; y < loop; ++y) {
DoSomething();
}
}
sendo equivalente a
for (x = 0; x < base*loop; ++x){
DoSomething();
}
Então, se você quiser um número de ninhos, ele pode ser escrito usando a divisão entre base e loop Portanto, poderia parecer algo tão simples assim:
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();
}
}
Então, se você digite printer(10, 2); Imprimiria:
00
01
02
03
04
...
97
98
99
Isso funcionou para mim muito bom - eu tive que selecionar de algumas alternativas, que foram armazenadas em mealternativepaths e a idéia básica é que eu estava tentando construir a próxima seleção e, quando houve um "transbordamento" em uma dimensão / componente, você apenas Reinacionam essa dimensão e adicione uma à outra.
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;
}
No interesse da concisão, estou colocando meu código aqui:
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);
}
Resultado
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
