4

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);
        }
    }
}
Improve this question

5 Answers 5

Reset to default
4

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.)

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

0

You can use a stack to make it iterative. In this stack you store your j variable. This should work.

void getPermutationsI(int v[], int n)
{
    int stack[100] = {0, 1, 2, 3, 4}; // you can do better, but I was lazy
    int k = 0;
    while (k >= 0)
    {
        if (k == n)
        {
            for (int i = 0; i < n; ++i)
                printf("%d ", v[i]);
            printf("\n");

            --k;
            swap(v[k], v[ stack[k] - 1 ]);
        }
        else
        {
            if (stack[k] < n)
            {
                swap(v[k], v[ stack[k] ]);
                ++stack[k];
                ++k;
            }
            else
            {
                stack[k] = k;
                --k;
                swap(v[k], v[ stack[k] - 1 ]);
            }
        }
    }
}
Improve this answer

5 Comments

Your solution is not based on the OP's approach, is it?
@Vlad - I think it is. It prints the permutations in the same order as his recursive function as far as I can tell. And the idea is the same.
well, not completely. At least the OP's algorithm makes two swaps on each step, and does nothing but printing when the stack depth is n.
@Vlad - I also make two swaps on the same step, if you consider a step to be an instance of a stack level. The OP's algorithm does one swap, then moves up the stack, then does another swap. This is the same as what I do. And it doesn't only print either, you think that's the only thing that happens because the details of returning from a function (moving down the stack) are abstracted. My --k is moving down the stack, which the recursive algorithm does automatically. As for the swap, that also happens in the OP's algorithm after returning / moving down the stack.
You have to move things around when going from recursive to iterative, there is no helping that. By using recursion, a lot of logic is abstracted by the programming language, which you have to make up for in the iterative implementation. If you printf what gets called and where in both programs, I think you'll find that the two are fully equivalent as far as the logic / idea is concerned.
0

In Python:

def perm_stack(s):
    st = []

    st.append((s,0))

    while not len(st)==0:

        t = st.pop()
        if t[1]==len(s):
            print t[0]
        else:
            for i in range(t[1], len(s)):
                s1 = swap(t[0], t[1], i)
                st.append((s1, t[1]+1))
Improve this answer

Comments

-1

You can use STL:

a[]={0,1,2,....n-1};
do{
    for(int i=0;i<n;++i)
      //  print v[ a[i] ]
    //print EOLN
}
while(next_permutation(a,a+n));

Not tested.

Improve this answer

2 Comments

The point is more to write an iterative version of the recursive algorithm than to solve the actual problem.
@Vlad - I thought it was obvious: this doesn't answer the question. Using next_permutation generates the permutations in a differen't order than the posted algorithm, so it's not the same.
-1

You need to read the chapter 7.2.1.2 of the TAOCP.

EDIT:
According to the discussion in the comments, a stack-based recursion elimination is good, too (although in my opinion it's not a pure iterative approach). Here is a draft of a stack-based version:

void getPermutationsNR(int v[]) 
{
    struct task
    {
        enum { swap, reccall } tasktype;
        int i, j;
    }
    stack<task> stack;
    stack.push(new task() {tasktype=reccall, i=0}); // initial task
    while (!stack.empty) // run task interpreter
    {
        task t = stack.pop();
        switch (t.tasktype)
        {
          case reccall:
            if (t.i == n) {/*display contents*/; break;}
            for (int j=t.i; j<n; j++)
            {
                stack.push(new task() {tasktype=swap, t.i, j});
                stack.push(new task() {tasktype=reccall, t.i+1});
                stack.push(new task() {tasktype=swap, t.i, j});
            }
            break;
          case swap:
            swap(v, t.i, t.j);
            break;
        }
    }
}
Improve this answer

14 Comments

As much as I prefer nudging answers to copyable algorithms for obvious homework questions, sending someone to a 4-volume tome without any further information regarding the question is not a helpful answer at all. -1 from me.
@sbi: First of all, TAOCP is 7-volume, not 4-volume. Second, the OP asks the question falsely believing the correct algorithm can be done by playing with the recursive solution, whereas it's not so. The TAOCP is the book which explains the problem in all its entirety, and analyses algorithms as much as possible. So my reference is the only correct one. Your opinion may differ, though. Then---go ahead and answer the question yourself. Better than Prof. Knuth did.
I see your point. Still. If you summarize the chapter's content as relevant to the question and then put that link in, I'd gladly upvote. Just linking directly to some text is bad enough. Linking to an article about the text you refer someone to is almost vicious.
@sbi: Searching TAOCP on Amazon is trivial. My link is there in order hint the OP that TAOCP is the developer's bible, just a book. Making a summary of the entire chapter is not a trivial task, I didn't do it before, and sorry, I am not going to do it for an upvote. Nevertheless, keeping your downvote in mind, are you going to present here something better than the chapter 7.2.1.2?
I'm getting the impression that it is impossible to solve my problem, and that I will learn why by reading 'chapter 7.2.1.2 of the TAOCP' - which I plan on doing. But that would require me to have the book, currently I need to know if I'm wasting my time.
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.