Thursday, September 11, 2008

Stack permutation

I was trying to solve a stack permutation problem in taocp. The question asks us to find no: of permutations of n numbers from 1...n that can be generated using a stack. The no:s 1...n can be pushed into the stack in that order only. When an element is popped of the stack, it is appended to an output queue. Once all elements are in output queue, the order of elements in the queue is a permutation obtained using stack.

For ex:- To obtain 2,3,1 from 1,2,3 we follow the sequence of operations
push 1,push 2,pop 2,push 3,pop 3,pop 1
Not all permutations can be obtained using the stack (for ex: - 3,1,2).

Let the no: of permutations of 1...n be a(n) with a(0) = 1 (only empty permutation possible with no numbers).

We have to find a(n+1)

Suppose that nl no:s appear to left of "1" and nr no:s to right of "1" in a permutation. The process of obtaining a permutation for those nl numbers to the left of "1" can be considered as permuting 2...(nl+1) using a stack (The "1" at the bottom of the stack can be ignored). This no: will be the same as no: of permutations possible for using a stack(Only the number of numbers matter).

Then no: of permutations possible for nl numbers to the left of "1" = a(nl).
Similarly no: of permutations possible for nr numbers to the right of "1" = a(nr).

For each of a(nl) permutations of numbers to the left, a(nr) permutations are possible for numbers to the right.
So a(nl)a(nr) permutations are possible for a particular position of "1" in the permutation.
Now nr = n - nl
So a(nl)a(nr) = a(nl)a(n-nl)

No: of elements to left of "1" can vary from 0...n.
So total number of permutations a(n+1) = sum(nl, 0, n) {a(nl)a(n-nl)} = a(0)a(n) + a(1)a(n-1) + .... + a(n)a(0)}

The term a(n) is simply the nth catalan number.

"Never believe in history, because history is created by those who win."


Anonymous said...

a delta improvement, which is obvious, still.. :)

a(n+1) = 2{a(0)a(n).....a(n/2)a(n/2)}


Balagopal said...

That works only if n+1 is even. Even if (n+1) is even, one of (n/2)s has got to be Ceil(n/2) and the other one floor(n/2).

sandeep-rb said...

This problem is equivalent to the problem of finding no. of different binary trees possible with n nodes.

Heres is the steps to find out a corresponding binary tree for a given stack permutation.

1. if there is no current node, create root node and label it as 'n'(corresponds to PUSH 1)
2. if the current node is not marked, create a left child and label it as 'n'
3. if the current node is marked, create a right child and label it as 'n'

POP n:
go to node 'n' and mark it.

Inorder traversal of this tree will be exactly the given stack permutation

similarly i believe we can find out equivalence between all problems whose solution is a catalan number (of course, this statement can be more generalized). there are enough equivalent problems listed in catalan numbers

conclusion: "The problem is only One, we delude it as many" :)