問(wèn)題描述

我正在編寫(xiě)一個(gè)代碼段，它遍歷 n 位數(shù)字的每個(gè)排列.例如，如果 n = 3，我想遍歷以下每個(gè)元素:

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 循環(huán)很容易編寫(xiě)代碼:

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 位數(shù)字.例如，如果 n = 10，我現(xiàn)在需要 10 個(gè)嵌套的 for 循環(huán).

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

我已經(jīng)考慮過(guò)這個(gè)問(wèn)題，并意識(shí)到可以使用遞歸解決問(wèn)題(深度優(yōu)先搜索一棵樹(shù)，每個(gè)節(jié)點(diǎn)有 10 個(gè)子節(jié)點(diǎn)，從 0 到 10，并在深度 n 處停止).但我的目標(biāo)是高性能，所以我不想因?yàn)殚_(kāi)銷(xiāo)而使用遞歸.我還有什么其他選擇?

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?

推薦答案

如果你想在不使用遞歸的情況下用單個(gè)循環(huán)模擬嵌套循環(huán)，你可以通過(guò)為每個(gè)循環(huán)變量維護(hù)一組狀態(tài)(或槽)來(lái)實(shí)現(xiàn)，這可以通過(guò)數(shù)組輕松完成.循環(huán)然后變成一個(gè)簡(jiǎn)單的問(wèn)題，即向該數(shù)組加 1"，根據(jù)需要執(zhí)行進(jìn)位操作.如果您的嵌套深度是 n，并且每個(gè)循環(huán)的最大邊界是 b，那么它的運(yùn)行時(shí)間是 O(b^n)，因?yàn)檫M(jìn)位操作只會(huì)最多花費(fèi)你 O(b^n)(我會(huì)在這里跳過(guò)代數(shù)).

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 的評(píng)論):

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

這篇關(guān)于C++:嵌套for循環(huán)的動(dòng)態(tài)數(shù)量(無(wú)遞歸)的文章就介紹到這了，希望我們推薦的答案對(duì)大家有所幫助，也希望大家多多支持html5模板網(wǎng)！