c：嵌套for循环的动态数量(没有递归)

我正在编写一个代码段,遍历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处停止).但我的目标是高性能,所以我不想因为开销而使用递归.我还有其他什么选择？

最佳答案

如果要在不使用递归的情况下使用单个模拟嵌套循环,可以通过为每个循环变量维护一组状态(或插槽)来实现,这可以通过数组轻松完成.循环然后变成一个简单的问题“向该数组添加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;
    }
}

点击查看更多相关文章

转载注明原文：c：嵌套for循环的动态数量(没有递归) - 乐贴网