c++ : dynamic number of nested for loops (without recursion)

Question

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

0, 0, 0

...

0, 1, 0

...

1, 0, 0

...

2, 3, 4

...

9, 9, 9

This is very easy to code using nested for loops:

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

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

I've thought about this and realized that the problem can be solved using recursion (depth first search through a tree, with each node having 10 children, 0 to 10, and stopping at depth n). But I'm aiming for high performance so I don't want to use recursion due to the overhead. What other alternatives do I have?

I know you're looking for high performance, but give this a read as the answer has some good information to consider. http://stackoverflow.com/questions/72209/recursion-or-iteration — jmstoker, Sep 11 '13 at 05:03
What makes you think that using for loops(complexity O(10^n)) will be efficient than using trie(some complexity in order of logn)?? — Saksham, Sep 11 '13 at 05:05
Why do you believe that recursion is slow? Did you benchmark? — Basile Starynkevitch, Sep 11 '13 at 05:07
You could set up an array (or something) of digits, then walk up and down it, Turing-style. Whether it would be much faster than recursion remains to be seen. — Beta, Sep 11 '13 at 05:12
For the record, you're going through a set of numbers, not through permutations. A permutation would be something like 123 213 132 321 312 231 — Cramer, Sep 11 '13 at 05:29
@BasileStarynkevitch, Recursion often has many other limits besides merely being slow. — Pacerier, Jun 03 '14 at 00:35
@Saksham. The complexity of m (=10) for loops of length n is O(n^m) = O(n^10), not O(10^n). — Brethlosze, Jul 06 '16 at 21:54

David Airapetyan · Answer 1 · 2016-03-19T00:21:17.867

If you want to simulate nested loops with a single one without using recursion, you can do so by maintaining a set of states (or slots) for each looping variable, which can be easily done with an array. Looping then turns into a simple matter of "adding 1" to that array, performing the carry operations as needed. If your nesting depth is n, and your maximum boundary for each loop is b, then the runtime of this is O(b^n), because the carry operations will only cost you at most O(b^n) (I'll skip the algebra here).

Here is the working C++ code (updated to integrate Drew's 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;
    }
}

Note that for the first `slots[index]++`, `index` will always be zero, so you can just do `slots[0]++`. — Drew McGowen, Mar 13 '16 at 07:49
@David, Actually, both m nested loops of length n and a single loop of length n^m will have O(n^m).... no algebra is required :) — Brethlosze, Jul 06 '16 at 21:47
@DavidAirapetyan Could you help to provide a piece of example code to use this function ? — SOUser, Oct 22 '18 at 08:58
Sure, here is a full example: https://gist.github.com/davidair/8cd9e906eeab26083a4a3727001830ff — David Airapetyan, Oct 22 '18 at 19:14

Dmitry Poroh · Answer 2 · 2013-09-11T09:29:08.773

In genreral case if you like to replace recursion to flat code you should use the stack (LIFO). So if you have 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 transform it to LIFO-based with saving local variables (str and i 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
    }
  }
}

score 3 · Answer 3 · answered Sep 11 '13 at 05:26

3

If you want the permutation for all the digits for a specific length;as you have shown example of 3 digits. Instead of running 3 nested loops, run a single loop of 10^3 which will give you all the permutations.

Split the number obtained into digits in each iteration if you want to use it for indexing.

Thus you will be needing just one loop rather than nested loops.

answered Sep 11 '13 at 05:26

Saksham

9,037
7
45
73

Simple and effective. – Cramer Sep 11 '13 at 05:28

c++ : dynamic number of nested for loops (without recursion)

3 Answers3

Linked

Related