转换递归置换发电机迭代 [英] Converting recursive permutation generator to iterative
问题描述
我有一些困难将这个递归算法，用于显示一组给定整数的所有排列为一个迭代。
无效getPermutationsR（INT v []，INT N，int i）以
{
如果（我== N）
{
//显示诉内容
}
其他
{
对于（INT J =; J＆n种; J ++）
{
交换（V，I，j）的;
getPermutationsR（V，N，I + 1）;
交换（V，I，j）的;
}
}
}
这是我目前的尝试，这是完全错误的，但我看不出有什么办法来纠正它，而无需使用原生的迭代算法问题。可以说，我尝试过我'啪'比'推'更（会导致一个错误，因为我试图访问的元素在一个空栈），另一半我是'推'比'啪'（无限循环）。
无效getPermutationsI（INT v []，INT N，int i）以
{
堆叠＆LT; INT＆GT; iStack技术;
堆叠＆LT; INT＆GT; jStack;
iStack.push（ⅰ）;
jStack.push（ⅰ）;
而（iStack.size（）大于0）
{
如果（iStack.top（）== N）
{
jStack.pop（）;
iStack.pop（）;
//显示诉内容
}
其他
{
对于（INT J = iStack.top（）; J＆n种; J ++）
{
//交换
//是与jStack
}
//交换
iStack.push第（i + 1）;
}
}
}
您所遇到的挑战是，你有函数调用和循环结构混合。这是很难理清这些。
首先，让我们先来代替流操作的所有控制与递归。
//你要开始getPermutionsR（V，N，0，0）
无效getPermutationsR（INT v []，int的N，诠释我，诠释J）
{
如果（我== N）
{
//显示诉内容
}
否则，如果（j == N）{
//什么也不做，我们跳出循环
}
其他
{
//这是循环内的递归调用。
//注意，我要送你到第一循环迭代在这里。
交换（V，I，j）的;
getPermutationsR（V，N，I + 1，I + 1）;
交换（V，I，j）的;
//而下一个循环周期
getPermutationsR（V，N，I，J + 1）;
}
}
接下来让我们添加的内部的，如果病情越状态，这样，我们只有一个递归调用。
//你要开始getPermutionsR（V，N，0，0，1）
无效getPermutationsR（INT v []，int的N，诠释我，诠释J，布尔华美通）
{
如果（我== N）
{
//显示诉内容
}
INT X = 1;
INT Y = J + 1;
如果（新华美通）{
交换（V，I，j）的;
X = 1 + 1;
Y = I + 1;
}
//我唯一的递归调用。请注意，我= n表示J =ñ。
如果（J＆n种）{
getPermutationsR（V，N，X，Y，华美通！）;
}
如果（新华美通）{
交换（V，I，j）的;
}
}
现在，我们已经做到了这一点，我们把它的形式，我们可以把它变成一个迭代版本以简单的方式。这里是转换
无效recursiveForm（参数，可以recursiveState）{
topHalf ...
如果（条件）{
recursiveForm（...）
}
bottomHalf ...
}
变为
无效iterativeForm（PARAMS）{
initializeStacks ...
pushStacks ...
topHalf ...
而（堆栈不为空）{
如果（条件）{
pushStacks ...
topHalf ...
}
其他 {
bottomHalf ...
popStacks ...
}
}
}
因此应用这种模式，我们得到的东西，如：
//你要开始getPermutionsR（V，N，0，0，1）
无效getPermutationsI（INT v []，INT N）
{
堆叠＆LT; INT＆GT; iStack技术;
堆叠＆LT; INT＆GT; jStack;
堆叠＆LT;布尔＆GT; firstCallStack;
// pushStacks与初始值
iStack.push（0）;
jStack.push（0）;
firstCallStack.push（1）;
// topHalf ...
如果（iStack.top（）== N）
{
//显示诉内容
}
INT X = iStack.top（）;
INT Y = jStack.top（）+ 1;
如果（firstCallStack.top（））{
交换（ⅴ，iStack.top（），jStack.top（））;
X = iStack.top（）+ 1;
Y = iStack.top（）+ 1;
}
而iStack.size（）＆GT; 0）{
//如果（条件）{
如果（jStack.top（）n种）{
// pushStacks ...
iStack.push（X）;
jStack.push（Y）;
firstCallStack.push（firstCallStack.top（）！）;
// topHalf ...
如果（iStack.top（）== N）
{
//显示诉内容
}
X = iStack.top（）;
Y = jStack.top（）+ 1;
如果（firstCallStack.top（））{
交换（ⅴ，iStack.top（），jStack.top（））;
X = iStack.top（）+ 1;
Y = iStack.top（）+ 1;
}
}
其他 {
// bottomHalf ...
如果（firstCallStack.top（））{
交换（ⅴ，iStack.top（），jStack.top（））;
}
}
}
}
（警告，所有code未经测试，而且可能甚至不会编译，但思路是正确的，而且是绝对相同的算法。）
I'm having some difficulty converting this recursive algorithm for displaying all the permutations of a given set of integers into an iterative one.
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);
}
}
}
This is my current attempt, it's completely wrong but I can't see any way to correct it without using a natively iterative algorithm for the problem . Half my attempts have had me 'popping' more than 'pushing' (Leads to an error as I attempt to access elements in an empty stack) and the other half I'm 'pushing' more than 'popping' (infinite loop).
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);
}
}
}
The challenge you are encountering is that you've got function calls and loop constructs intermingled. It is hard to disentangle those.
First let's start by replacing all control of flow operations with recursion.
// 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);
}
}
Next let's add more state so that we only have one recursive call inside of an if condition.
// 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);
}
}
Now that we've accomplished this, we have it in a form where we can transform it into an iterative version in a straightforward way. Here is the transformation
void recursiveForm (params, recursiveState) {
topHalf...
if (cond) {
recursiveForm(...)
}
bottomHalf...
}
becomes
void iterativeForm(params) {
initializeStacks...
pushStacks...
topHalf...
while (stacks not empty) {
if (cond) {
pushStacks...
topHalf...
}
else {
bottomHalf...
popStacks...
}
}
}
So applying that pattern we get something like:
// 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());
}
}
}
}
(Warning, all code untested, and may well not even compile. But the idea is correct. And it is definitely the same algorithm.)
这篇关于转换递归置换发电机迭代的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
