C++:嵌套for循环的动态数量(无递归)

2021-12-11 00:00:00 递归 performance for-loop tree c++

我正在编写一个代码段，它遍历 n 位数字的每个排列.例如，如果 n = 3，我想遍历以下每个元素:

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

使用嵌套的 for 循环很容易编写代码:

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)

但我想将其概括为 n 位数字.例如，如果 n = 10，我现在需要 10 个嵌套的 for 循环.

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

我已经考虑过这个问题，并意识到可以使用递归解决问题(深度优先搜索一棵树，每个节点有 10 个子节点，从 0 到 10，并在深度 n 处停止).但我的目标是高性能，所以我不想因为开销而使用递归.我还有什么其他选择?

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?

推荐答案

如果你想在不使用递归的情况下用单个循环模拟嵌套循环，你可以通过为每个循环变量维护一组状态(或槽)来实现，这可以通过数组轻松完成.循环然后变成一个简单的问题，即向该数组加 1"，根据需要执行进位操作.如果您的嵌套深度是 n，并且每个循环的最大边界是 b，那么它的运行时间是 O(b^n)，因为进位操作只会最多花费你 O(b^n)(我会在这里跳过代数).

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

这是工作的 C++ 代码(更新以整合 Drew 的评论):

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

相关文章