C ++: dynamic number of nested loops (no recursion)

Question

I am writing a code segment that iterates through each permutation of n digits. So, for example, if n = 3, I would like to iterate over each of the following elements:

0, 0, 0

...

0, 1, 0

...

one hundred

...

2, 3, 4

...

9, 9, 9

This is very easy to code with nested loops:

for(digit1 0 to 9) for(digit2 0 to 9) for(digit3 0 to 9) 

But I want to generalize this to n digits. If, for example, n = 10, I now need 10 nested loops.

I thought about it and realized that the problem can be solved using recursion (first, search for depth through a tree, with each node having 10 children, from 0 to 10 and stops at a depth of n). But I strive for high performance, so I do not want to use recursion due to overhead. What other alternatives do I have?

Answer 1

If you want to simulate nested loops with one without recursion, you can do this by maintaining a set of states (or slots) for each loop variable, which can easily be done using an array. Then the loop turns into a simple “add 1” question to this array, performing carry operations if necessary. If your nesting depth is n, and your maximum border for each cycle is b, then the execution time is O (b ^ n), because the transfer operations will cost you no more than O (b ^ n) (I will skip the algebra here) .

Here is the working C ++ code ( updated to include Drew comment):

 void IterativeNestedLoop(int depth, int max) { // Initialize the slots to hold the current iteration value for each depth int* slots = (int*)alloca(sizeof(int) * depth); for (int i = 0; i < depth; i++) { slots[i] = 0; } int index = 0; while (true) { // TODO: Your inner loop code goes here. You can inspect the values in slots // Increment slots[0]++; // Carry while (slots[index] == max) { // Overflow, we're done if (index == depth - 1) { return; } slots[index++] = 0; slots[index]++; } index = 0; } } 

Answer 2

If you need a permutation for all digits for a certain length, as you showed an example of 3 digits. Instead of running 3 nested loops, run one loop of 10 ^ 3, which will give you all the permutations.

Divide the number obtained by the numbers at each iteration if you want to use it for indexing.

This way you only need one loop, not nested loops.

Answer 3

In the normal case, if you want to replace recursion with flat code, you should use the stack (LIFO). So, if you have a recursive algorithm:

 void print(std::string str, int depth) { if (depth == n) { std::cout << str << std::endl; return; } for (int i = 0; i < 10; ++i) { char val[2] = { i + '0', 0 }; print(str + val + ", ", depth+1); } } 

You can convert it to LIFO-based while preserving local variables (str and me in this case):

 struct StackItem { StackItem(const std::string& ss, unsigned ii) : str(ss), i(ii) {} std::string str; int i; }; void print_norec() { std::list< StackItem > stack; stack.push_back(StackItem("", 0)); while (!stack.empty()) { StackItem& current = stack.back(); if (stack.size() == n+1) { std::cout << current.str << std::endl; stack.pop_back(); // return from "recursive" function continue; } if (current.i < 10) { char val[2] = { current.i + '0', 0 }; // call "recursive" function stack.push_back(StackItem(current.str + val + ", ", 0)); current.i++; } else { stack.pop_back(); // return from "recursive" function } } }