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

一尘不染

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

algorithm

我很难将这种递归算法转换为将给定整数集的所有排列显示为迭代值。

void getPermutationsR(int v[], int n, int i) 
{
    if (i == n)
    {
        //Display contents of v
    } 
    else
    {
        for (int j=i; j<n; j++) 
        {
            swap (v, i, j);
            getPermutationsR(v, n, i+1);
            swap (v, i, j);
        }
    }
}

这是我目前的尝试，这是完全错误的，但是如果不使用本机迭代算法来解决问题，我将看不到任何纠正方法。一半的尝试使我“弹出”而不是“推动”（当我尝试访问空堆栈中的元素时导致错误），另一半则使我的“推动”比“弹出”更多（无限循环）。

void getPermutationsI(int v[], int n, int i) 
    {
    stack<int> iStack;
    stack<int> jStack;

    iStack.push(i);
    jStack.push(i);

    while(iStack.size() > 0)
    {
        if (iStack.top() == n)
        {
            jStack.pop();
            iStack.pop();
            //Display contents of v
        }
        else
        {
            for (int j = iStack.top(); j < n; j++)
            {
               //swap 
                               //something to do with jStack
            }
            //swap 
            iStack.push(i+1);
        }
    }
}

阅读 264

2020-07-28

共1个答案

一尘不染

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

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

// 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());
            }
        }
    }
}

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

2020-07-28