Make nested for loop algorithm - dynamic

Question

I have an algorithm that goes something like this:

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

How can I write this iteratively, making it dynamic, such that I don't limit myself to a fixed number of for loops (i, j, k, l, m) (i.e. I can do (i) or (i, j) or (i, j, k) or (i, j, k, l) etc...)?

(I am strictly seeking answers with dynamic, iterative solutions. If you do not understand this, please continue reading, starting with the previous sentence.)

Answer 1

You probably want recursion.

Answer 2

Call the variables i[0] ... i[n] initialize them all to 1. To increment at each step do

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

Essentially you are implementing a binary counter clearing all the set bits less than the first clear bit, then setting the first clear bit. This runs the do somethings in the same order as the given loop.

You can do similar things with different ranges, the ranges of each i[j] need not even be the same.

Edit added initialization.

Note Recursion is probably overkill here, and is somewhat less flexible than the flat implementation (consider aborting from the inner loop.). This is a problem that comes up often in practice, and is not all that complicated. What we want to do is to have each loop look like

for i = 1 to 2
   do beginning stuff with i
   do inner loop
   do ending stuff with i
next

If we just consider the index variables we have what looks like a binary counter. If we look at the values of the index variables when we perform the innermost loop.

 i j k l
 1 1 1 1
 1 1 1 2
 1 1 2 1

implementing a counter is easy. If we just label our variables, innermost first, so that i -> i[3], j -> i[2], k -> i[1] and l -> [0] then a single incrementing step consists of

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

now, let us do the stuff at the end of the loop. This is easy, the end of the loop happens just before we increment. So our incrementer looks like

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

Now, the tricky part. It at first appears that we do the beginning stuff just after incrementing, but this has two problems.

1. It misses the initial increments (the ones that happen when we set the initial variables to 1
2. It calls inital increment routines for everything on the final increment.

(these are essentially the same problem)

the solution to the first is easy, we just call beginning stuff outside the main loop.

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

Now to get the other initializers we do them after we have incremented the count.

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]

This takes no overhead (call stack, etc) over the nested loop version. It makes it easy to abort from deep in the nest. It is a bit tricky, but I'd be surprised if it is more complicated than the recursive version with an explicit stack. De gustibus non disputandum est.

Answer 3

Write your algorithm exactly as you would using recursion, but use an explicit stack object instead of recursion. I.e.:

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 4

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

Far more elegant, shorter, less tricky than any iterative solution you can come up with. Downvote me all ya want, doesn't make it less true.

Answer 5

I would upvote deinst's solution, but I'm new and don't have the 15 rep... After tracing each algorithm, I do believe deinst has the correct dynamic-iterative approach. However, deinst initializes all at once at the start, while roygbiv initializes repeatedly within the loop nest. (I think I had seen a correct prior edit of deinst's.)

Answer 6

You can construct a collection of sequences, where each sequence is a permutation of your loop variables i,j,k,...

Once you have this collection, you can then iterate:

foreach (var seq in myCollection)
{
  initialize(seq[0]);
  initialize(seq[1]);
  initialize(seq[2]);
  ...
  doSomething(...);
}

One way to generate the collection of sequences, courtesy of Eric Lippert, via 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}));                
}

You pass a sequence {{1,2},{1,2},...{1,2}} of any length, where each inner {1,2} sequence replaces one of your loop variables, and you get back a sequence of all permutations of the values.

Answer 7

You will need to keep track of depth variables where depth is the total depth of your nesting. You can use an array or stack for that, or you can use the power of recursion and get away with allocating a single local variable at a time

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

Since i,j,k,... range from 1 to 2, it might also be possible to interpret them as bits of a single integer variable.

Note that your nested loops perform 2^depth operations in total.

Answer 8

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

Still way trickier than recursion. Don't use this unless you absolutely have to.