时间:2019-05-01 标签:c++: dynamic number of nested for loops (without recursion)

Question

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

0, 0, 0

...

0, 1, 0

...

1, 0, 0

...

2、3、4

...

9、9、9

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

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

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

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

Answer 1

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

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

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