将递归置换生成器转换为迭代

将递归置换生成器转换为迭代

您遇到的挑战是您已经混合了函数调用和循环结构。很难解开这些。

首先，让我们以递归替换所有对流 *** 作的控制。

// You'll want to start with getPermutionsR(v, n, 0, 0)void getPermutationsR(int v[], int n, int i, int j) {    if (i == n)    {        //Display contents of v    }    else if (j == n) {        // By doing nothing, we break out of the loop    }    else    {        // This was your recursive call inside of the loop.        // Note that I'm sending you to to the first loop iteration here.        swap (v, i, j);        getPermutationsR(v, n, i+1, i+1);        swap (v, i, j);        // And the next loop iteration        getPermutationsR(v, n, i, j+1);    }}

接下来，让我们添加更多状态，以便在if条件内只有一个递归调用。

// You'll want to start with getPermutionsR(v, n, 0, 0, 1)void getPermutationsR(int v[], int n, int i, int j, bool firstCall){    if (i == n)    {        //Display contents of v    }    int x = i;    int y = j+1;    if (firstCall) {        swap (v, i, j);        x = i+1;        y = i+1;    }    // My one recursive call.  Note that i=n implies j=n.    if (j < n) {        getPermutationsR(v, n, x, y, !firstCall);    }    if (firstCall) {        swap (v, i, j);    }}

既然我们已经完成了这一步，就可以将其以一种简单的方式将其转换为迭代版本的形式。这是转型

void recursiveForm (params, recursiveState) {    topHalf...    if (cond) {        recursiveForm(...)    }    bottomHalf...}

变成

void iterativeForm(params) {    initializeStacks...    pushStacks...    topHalf...    while (stacks not empty) {        if (cond) { pushStacks... topHalf...        }        else { bottomHalf... popStacks...        }    }}

因此，应用该模式，我们得到如下结果：

// You'll want to start with getPermutionsR(v, n, 0, 0, 1)void getPermutationsI(int v[], int n){    stack<int> iStack;    stack<int> jStack;    stack<bool> firstCallStack;    // pushStacks with initial value    iStack.push(0);    jStack.push(0);    firstCallStack.push(1);    // topHalf...    if (iStack.top() == n)    {        //Display contents of v    }    int x = iStack.top();    int y = jStack.top()+1;    if (firstCallStack.top()) {        swap (v, iStack.top(), jStack.top());        x = iStack.top()+1;        y = iStack.top()+1;    }    while iStack.size() > 0) {        // if (cond) {        if (jStack.top() < n) { //pushStacks... iStack.push(x); jStack.push(y); firstCallStack.push(!firstCallStack.top()); // topHalf... if (iStack.top() == n) {     //Display contents of v } x = iStack.top(); y = jStack.top()+1; if (firstCallStack.top()) {     swap (v, iStack.top(), jStack.top());     x = iStack.top()+1;     y = iStack.top()+1; }        }        else { // bottomHalf... if (firstCallStack.top()) {     swap (v, iStack.top(), jStack.top()); }        }    }}

（警告，所有代码都未经测试，甚至可能无法编译。但是这个想法是正确的。而且绝对是相同的算法。）