Напишите свой алгоритм точно так же, как при использовании рекурсии, но используйте явный объект стека вместо рекурсии. То есть: [
var stack = new Stack();
stack.Push(InitialThingy);
while(stack.Count != 0)
{
var currentItem = stack.Pop();
//Do things to current item and add things to stack as we go.
}
private sub doStuff(depth as integer)
for i as integer = 1 to 2
initialize(work_item(i))
if depth > 1 then doStuff(depth - 1)
doSomething(work_item(i))
next
end sub
Намного более элегантно, короче и менее хитроумно, чем любое итеративное решение, которое вы можете придумать. Голосуйте против меня, сколько хотите, не делает это менее правдивым.
Я бы проголосовал за решение deinst, но я новичок и у меня нет 15 репостов... Проследив каждый алгоритм, я считаю, что у deinst правильный динамически-итеративный подход. Однако deinst инициализирует все сразу в начале, в то время как roygbiv инициализирует многократно в пределах гнезда цикла. (Мне кажется, я видел правильную предыдущую правку deinst'а)
.Вызов переменных i [0] ... i [n] инициализируйте их все до 1. Для увеличения на каждом шаге выполните
int j, k;
for(j = n - 1; j >= 0; j--){
initialize(i[j]);
}
while (true) {
j = 0;
while (i[j] == 2) {
doSomething(i[j]);
j++;
}
if (j < n) {
doSomething(i[j]);
} else {
break;
}
for (j = 0; j < n; j++) {
if (i[j] == 1) {
i[j] = 2;
break;
}
else {
i[j] = 1;
}
}
if (j == n) break;
for (k = j; k >= 0; k--) {
initialize(i[k]);
}
}
По сути, вы реализуете двоичный счетчик, очищающий весь набор бит меньше, чем первый бит очистки, затем устанавливается первый бит очистки. Это запускает do somethings в том же порядке, что и данный цикл.
Вы можете делать аналогичные вещи с разными диапазонами, диапазоны каждого i [j] даже не обязательно должны быть одинаковыми.
Правка добавлена инициализация.
Примечание Рекурсия здесь, вероятно, излишня, и она несколько менее гибкая, чем плоская реализация (рассмотрите возможность прерывания из внутреннего цикла.). Это проблема, которая часто возникает на практике, и в ней нет ничего сложного. Что мы хотим сделать, так это сделать так, чтобы каждый цикл выглядел как
for i = 1 to 2
do beginning stuff with i
do inner loop
do ending stuff with i
next
. Если мы просто рассмотрим индексные переменные, у нас будет то, что выглядит как двоичный счетчик. Если мы посмотрим на значения индексных переменных при выполнении самого внутреннего цикла.
i j k l
1 1 1 1
1 1 1 2
1 1 2 1
реализовать счетчик несложно.Если мы просто помечаем наши переменные, сначала самые внутренние, так что i -> i [3]
, j -> i [2]
, k -> i [1]
и l -> [0]
тогда один шаг увеличения состоит из
j = 0
while i[j] == 2
i[j] = 1
j++
if j == maxindex
break out, we're done with all the loops
else
i[j] = 2
, давайте сделаем все в конце цикла. Это просто, конец цикла происходит непосредственно перед тем, как мы увеличиваем. Итак, наш инкрементатор выглядит как
j = 0
while i[j] == 2
do ending stuff with i[j]
i[j] = 1
j++
if j == maxindex
break out, we're done with all the loops
else
do ending stuff with i[j]
i[j] = 2
Теперь сложная часть. На первый взгляд кажется, что мы выполняем начальные действия сразу после увеличения, но здесь есть две проблемы.
(по сути, это одна и та же проблема)
Решение первого простое, мы просто вызываем начальный материал вне основного цикла.
for j = maxindex - 1 downto 0
do beginning stuff with i[j]
while true
j = 0
while i[j] == 2
do ending stuff with i[j]
i[j] = 1
j++
if j == maxindex
break out, we're done with all the loops
else
do ending stuff with i[j]
i[j] = 2
Теперь, чтобы получить другие инициализаторы, мы выполняем их после увеличения счетчика.
for j = maxindex - 1 downto 0
do beginning stuff with i[j]
while true
j = 0
while i[j] == 2
do ending stuff with i[j]
i[j] = 1
j++
if j == maxindex
break out, we're done with all the loops
else
do ending stuff with i[j]
i[j] = 2
for k = j downto 0
do beginning stuff with i[k]
Это не требует накладных расходов (стек вызовов и т. д.) над версией вложенного цикла. Это упрощает прерывание из глубины гнезда. Это немного сложно, но я был бы удивлен, если бы это было сложнее, чем рекурсивная версия с явным стеком. De gustibus non disputandum est.
Вам нужно отслеживать depth
переменные, где depth
- общая глубина вложенности. Для этого можно использовать массив или стек, а можно воспользоваться силой рекурсии и обойтись выделением одной локальной переменной за раз
function doEverything(depth) {
if (depth == 0) return;
var i; // a new local variable on each call
for i = 1 to 2 {
initialize(work_item(i));
doEverything(depth-1);
doSomething(work_item(i));
}
}
Поскольку i,j,k,...
варьируются от 1 до 2, их также можно интерпретировать как биты одной целочисленной переменной.
Обратите внимание, что ваши вложенные циклы выполняют в общей сложности 2^глубины
операций.
void doStuff(int depth)
{
int i[depth];
int sp = depth - 1;
i[sp] = 0;
while (1)
{
if (++i[sp] <= 2) // "next". This is why we init to 0.
{ // At this point, i[sp] is 1 or 2.
// init item i[sp];
if (sp) // If there's space to nest another loop
{
i[--sp] = 0; // Push a 0
continue; // Start iterating with the new 0 as TOS
}
}
else if (++sp >= depth) // Here, i[sp] is 3. Leave the inner loop
break; // and exit if stack's now empty
// use item i[sp];
}
}
Все еще сложнее, чем рекурсия. Не используйте это без крайней необходимости.
Вы можете создать коллекцию последовательностей, каждая из которых представляет собой перестановку переменных цикла i, j, k, ...
Получив эту коллекцию, вы можете выполнить итерацию:
foreach (var seq in myCollection)
{
initialize(seq[0]);
initialize(seq[1]);
initialize(seq[2]);
...
doSomething(...);
}
Один из способов сгенерировать коллекцию последовательностей, любезно предоставленную Эриком Липпертом , через LINQ:
static IEnumerable<IEnumerable<T>> CartesianProduct<T>(this IEnumerable<IEnumerable<T>> sequences)
{
IEnumerable<IEnumerable<T>> emptyProduct = new[] { Enumerable.Empty<T>() };
return sequences.Aggregate(
emptyProduct,
(accumulator, sequence) =>
from accseq in accumulator
from item in sequence
select accseq.Concat(new[] {item}));
}
Вы передаете последовательность {{1,2}, {1,2}, ... {1,2}} из любой длины, где каждая внутренняя последовательность {1,2} заменяет одну из ваших переменных цикла, и вы получаете обратно последовательность всех перестановок значений.