c ++：嵌套for循环的动态数（无递归） [英] c++ : dynamic number of nested for loops (without recursion)

问题描述

我正在写一个代码段，遍历n个数字的每个排列。例如，如果n = 3，我将要遍历以下每个元素：

0,0,0

...

0，1，0

...

1，0，0

...

2，3，4

...

9，9，9

这是很容易使用嵌套的循环代码：

  for（digit1 0到9） 
 for（digit2 0 to 9）
 for（digit3 0 to 9）
  

但我想把这个n个数字。如果例如n = 10，我现在需要10个嵌套for循环。

我想到了这一点，意识到问题可以使用递归（深度优先搜索通过树，每个节点有10个孩子，0到10，并停在深度n）。但我的目标是高性能，所以我不想使用递归，由于开销。

如果你想用一个模拟嵌套循环，而不使用递归，你可以做因此通过为每个循环变量维持一组状态（或槽），这可以容易地用数组来完成。循环然后变成对该数组加1的简单事情，根据需要执行进位操作。如果你的嵌套深度是 n ，并且每个循环的最大边界是 b ，那么这个运行时间是O（b ^ n）

这里是工作的C ++代码（更新）。集成Drew的注释）：

  void IterativeNestedLoop（int depth，int max）
 {
 //初始化槽以保存每个深度的当前迭代值
 int * slots =（int *）alloca（sizeof（int）* depth）; 
 for（int i = 0; i  {
 slots [i] = 0; 
} 
 
 int index = 0; 
 while（true）
 {
 // TODO：你的内循环代码在这里。你可以检查槽中的值
 
 //增量
 slots [0] ++; 
 
 //载入
 while（slots [index] == max）
 {
 //溢出，我们完成
 if（index = = depth  -  1）
 {
 return; 
} 
 
 slots [index ++] = 0; 
 slots [index] ++; 
} 
 
 index = 0; 
} 
} 
  

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?

解决方案

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

这篇关于c ++：嵌套for循环的动态数（无递归）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！