Сделать вложенным для цикла алгоритм - динамический

Question

У меня есть алгоритм, который выглядит примерно так:

for m = 1 to 2
  initialize(work_item(m))
  for l = 1 to 2
    initialize(work_item(l))
    for k = 1 to 2
      initialize(work_item(k))
      for j = 1 to 2
        initialize(work_item(j))
        for i = 1 to 2
          initialize(work_item(i))
          doSomething(work_item(i))
        next
        doSomething(work_item(j))
      next
      doSomething(work_item(k))
    next
    doSomething(work_item(l))
  next
  doSomething(work_item(m))
next

Как я могу написать это итеративно, сделав его динамичным, чтобы я не ограничивал себя фиксированным числом циклов for (i, j, k, l, m) (т.е. я могу делать (i) или ( i, j) или (i, j, k) или (i, j, k, l) и т. д ...)?

(Я строго ищу ответы с динамическими итеративными решениями. Если вы этого не понимаете, пожалуйста, продолжайте читать, начиная с предыдущего предложения.)

Answer 1

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

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

Answer 2

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

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

Answer 3

Вы, вероятно, хотите рекурсия .

Answer 4

Я бы одобрил решение deinst, но я новичок и у меня нет 15 представителей ... После отслеживания каждого алгоритма, я считаю, что deinst имеет правильный динамически-итеративный подход.Однако deinst инициализирует все сразу при запуске, в то время как roygbiv инициализирует повторно в гнезде цикла.(Я думаю, что видел правильное предварительное редактирование deinst's.)

Answer 5

Вызовите переменные 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 dothings в том же порядке, что и данный цикл.

Вы можете делать похожие вещи с разными диапазонами, диапазоны каждого 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

Теперь сложная часть. Сначала кажется, что мы делаем начальные вещи только после увеличения, но это имеет две проблемы.

1. Он пропускает начальные приращения (те, которые происходят, когда мы устанавливаем начальные переменные в 1
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.

Answer 6

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

Все еще хитрее, чем рекурсия. Не используйте это, если вам абсолютно не нужно.

Answer 7

Вам нужно будет отслеживать 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^depth операций.

Answer 8

Вы можете создать коллекцию последовательностей, где каждая последовательность представляет собой перестановку переменных вашего цикла 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} заменяет одну из ваших переменных цикла, и вы получаете последовательность всех перестановок значений.