Другими словами, могу ли я сделать что-то вроде
for() {
for {
for {
}
}
}
За исключением N раз? Другими словами, когда вызывается метод создания циклов, ему задан некоторый параметр N, и тогда метод будет создавать N этих циклов, вложенных один в другой?
Конечно, идея состоит в том, что должен быть "простой" или "обычный" способ сделать это. У меня уже есть идея для очень сложного.
Похоже, что вы можете посмотреть в рекурсия.
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
Возможно, вы захотите объяснить, что вы действительно хотите сделать.
Если внешние циклы 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();
}
Я действительно думал об этом на днях.
Пример, который, вероятно, не идеален, но довольно близок к тому, что мне кажется, будет печатать дерево каталогов
public void printTree(directory) {
for(files in directory) {
print(file);
if(file is directory) {
printTree(file);
}
}
}
таким образом вы получаете стек для циклов, вложенных друг в друга, без хлопот, чтобы выяснить, как именно они должны идти вместе.
2015 Edit: В то же время, что и предыдущее заклинание, я сделал следующий пакет для обработки этого; 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,...) по (1,...); но нужно указать (...).
Файл NForTest должен демонстрировать несколько способов его использования.
Основная предпосылка этого заключается в том, чтобы просто продвигать "индексы" на каждом повороте, а не на использование рекурсии.
Проблема требует дополнительной спецификации. Возможно, рекурсия поможет вам, но имейте в виду, что рекурсия почти всегда является альтернативой итерации, и наоборот. Возможно, для ваших потребностей может быть достаточно двухуровневой вложенной петли. Просто сообщите нам, какую проблему вы пытаетесь решить.
Существенной идеей создания циклов вложенности является умножение.
Развернувшись на Michael Burr, ответьте, если внешние циклы 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>>. Затем вы можете перебирать этот список с помощью одного цикла.
Функциональная библиотека 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 первоклассным, следующим образом. Пусть say 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-loop и собрать результаты всех приложений doSomething:
List<String> s = xs.map(P.p3()).apply(ys).apply(zs).map(doSomething);
Если у вас общая структура вложенных циклов, например:
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].
Самый простой общий подход, который я мог бы найти в 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);
}
}
}
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();
}
Создает хороший сложенный скелет for-loop;-) Не совсем серьезно, и я знаю, что рекурсивное решение было бы более элегантным.
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);
}
}
Пример вызова:
int[] ranges = {2, 2, 2};
recursiveFor(new ArrayDeque<Integer>(), ranges, ranges.length);
мой первый раз отвечая на вопрос, но я чувствовал, что мне нужно поделиться этой информацией из `
for (x = 0; x < base; ++x) {
for (y = 0; y < loop; ++y) {
DoSomething();
}
}
эквивалентно
for (x = 0; x < base*loop; ++x){
DoSomething();
}
поэтому, если вам нужно n число гнезд, его можно записать с помощью разделения между base и loop, чтобы он выглядел так просто:
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();
}
}
поэтому, если бы вы набрали printer(10, 2);, он распечатал:
00
01
02
03
04
...
97
98
99
Это сработало для меня очень хорошо - мне пришлось выбирать из нескольких альтернатив, которые были сохранены в 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;
}
В интересах краткости я размещаю свой код здесь:
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);
}
Выход
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