Есть ли способ сделать n-уровневые вложенные циклы в Java?

Question

Другими словами, могу ли я сделать что-то вроде

for() {
    for {
       for {
       }
    }
}

Кроме N раз? Другими словами, когда вызывается метод, создающий циклы, ему присваивается некоторый параметр N, и метод затем создает N из этих циклов, вложенных друг в друга?

Конечно, идея заключается в том, что должен быть «простой» или «обычный» способ сделать это. У меня уже есть идея для очень сложной.

Answer 1

jjnguy прав; рекурсия позволяет динамически создавать вложенность переменной глубины. Тем не менее, вы не получите доступ к данным из внешних слоев без дополнительной работы. Случай с вложенным вложением:

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**
        }
    }
}

сохраняет переменные i, j и k в области видимости для использования самым внутренним телом.

Вот один быстрый способ сделать это:

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];
            }
        }
    }
}

Интерфейс IAction определяет роль управляемого действия, которое принимает массив индексов в качестве аргумента для своего метода act.

В этом примере каждый экземпляр NestedFor настраивается конструктором с ограничениями итерации и действием, которое будет выполняться на самом внутреннем уровне. Параметр метода nFor указывает, как глубоко вложить.

Вот пример использования:

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);
    }
}

и (частичный) вывод его выполнения:

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

Answer 2

Звучит так, как будто вы хотите посмотреть рекурсию.

Answer 3

Возможно, вы захотите объяснить, что вы действительно хотите сделать.

Если внешние циклы for не выполняют ничего, кроме управления счетом, то ваши вложенные циклы for являются просто более сложным способом итерации по счетчику, который может обрабатываться одним циклом for.

Например:

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

Эквивалентно:

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

Answer 4

2015 Редактировать: Наряду с тем же тщеславием, что и предыдущее заклинание, я сделал следующий пакет для обработки этого; https://github.com/BeUndead/NFor

Использование будет следующим:

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));
    }
}

в результате

[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]

Он также поддерживает условия, отличные от lessThan. Использование там быть (с 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));

В результате:

[-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]

Очевидно, что поддерживаются циклы разной длины и разных классов (все в штучной упаковке, числовые примитивы). По умолчанию (если не указано) используется значение (0, ...). By (1, ...); но должно быть указано a to (...).

Файл NForTest должен демонстрировать несколько различных способов его использования.

Основной предпосылкой этого является простое продвижение «индексов» каждый ход, а не использование рекурсии.

Answer 5

Я действительно думал об этом на днях.

Примером, который, вероятно, не идеален, но довольно близок к тому, о чем я думаю, было бы распечатать дерево каталогов

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

Таким образом, вы получаете стопку циклов for, вложенных друг в друга, без необходимости точно определять, как они должны идти вместе.

Answer 6

Основная идея вложенных циклов - умножение .

Если продолжить ответ Михаэля Барра, если внешние циклы for не делают ничего, кроме управления счетом, то ваши вложенные циклы for над счетами n - это просто более сложный способ перебора произведения счетчиков. с одной петлей for.

Теперь давайте расширим эту идею до списков. Если вы перебираете три списка во вложенных циклах, это просто более сложный способ перебора продуктов списков с помощью одного цикла. Но как выразить произведение трех списков?

Во-первых, нам нужен способ выражения произведения типов. Произведение двух типов X и Y может быть выражено как универсальный тип, такой как P2<X, Y>. Это просто значение, которое состоит из двух значений: одно типа X, другое типа Y. Это выглядит так:

public abstract class P2<A, B> {
  public abstract A _p1();
  public abstract B _p2();
}

Для продукта трех типов у нас просто есть P3<A, B, C> с очевидным третьим методом. Таким образом, произведение трех списков достигается путем распределения функтора List по типу продукта. Таким образом, произведение List<X>, List<Y> и List<Z> просто List<P3<X, Y, Z>>. Затем вы можете перебрать этот список с помощью одного цикла.

Библиотека Functional Java имеет тип List, который поддерживает умножение списков вместе, используя первоклассные функции и типы продуктов (P2, P3 и т. Д., Которые также включены в библиотеку).

Например:

for (String x : xs) {
   for (String y : ys) {
     for (String z : zs) {
       doSomething(x, y, z);
     }
   }
}

Эквивалентно:

for (P3<String, String, String> p : xs.map(P.p3()).apply(ys).apply(zs)) {
   doSomething(p._1(), p._2(), p._3());
}

Продвигаясь дальше с функциональной Java, вы можете сделать doSomething первоклассным, как показано ниже. Допустим, doSomething возвращает строку:

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());
    }
  };

Затем вы можете полностью исключить цикл for и собрать результаты всех применений doSomething:

List<String> s = xs.map(P.p3()).apply(ys).apply(zs).map(doSomething);

Answer 7

Проблема требует уточнения. Возможно, рекурсия поможет вам, но имейте в виду, что рекурсия почти всегда является альтернативой итерации, и наоборот. Может быть так, что двухуровневый вложенный цикл может быть достаточным для ваших нужд. Просто дайте нам знать, какую проблему вы пытаетесь решить.

Answer 8

Если у вас общая структура вложенного цикла, например:

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);

где i0,i1,i2,...,id - переменные цикла, а d - глубина вложенного цикла.

Эквивалентное рекурсивное решение:

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 - это массив размером d, представляющий соответствующие переменные i0,i1,i2,...id соответственно int counters[d].

nestedToRecursion(counters,0);

Подобным образом мы можем преобразовать другие переменные, такие как инициализация рекурсии или окончание, используя для них массивы, то есть мы могли бы иметь initial[d], ending[d].

Answer 9

Самый общий подход, который я смог придумать в 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] );
    }
}

Или в 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]; } 
);

Реализация, которая поддерживает это:

/**
 * 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);
        }
    }
}

Answer 10

Это сработало для меня очень хорошо - мне пришлось выбирать из некоторых альтернатив, которые были сохранены в myAlternativePaths, и основная идея заключается в том, что я пытался создать следующий выбор, и когда было «переполнение» в одном измерении / компоненте вы просто заново инициализируете это измерение и добавляете одно к следующему.

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;
}