I have a Stack1 which has the entries a,b,c ( with a on the Top) and Stack2 which is empty.The condition is.

An entry pooped out of the stack1 can be printed immediatly or pushed to stack2. An Entry popped out of the stack2 can only be printed.

In this Arrangement, which of the permutation of a,b,c is not possible.

I tried diagrammatically by popping out the initial stack and found the first arrangement as c,a,b...Then i mind a formula taught in Permutation's course as (n-1)! possibilites so came up with answer of 5.

so, which arrangement will be not possible.??


This process is called stack sorting. Wikipedia has a page on the subject.

Here you read that the number of possible sequences when the input is $1,2,\dots,n$ equals the Catalan number $C_n = \frac{1}{n+1} {2n\choose n}$, which differs from your guess.

In fact there is a nice characterization of the orders which are possible, they avoid the permutation pattern $231$. However your problem is "backwards", not the strings that can be sorted using a single stack, but the strings that can be obtained that way.

| cite | improve this answer | |
  • $\begingroup$ But that's true and i had a read ..it's all about 'numbers' what if i was asked regrading the possible permutations not about Catalan number @Hendrik Jan $\endgroup$ – tonny Nov 4 '14 at 18:02
  • $\begingroup$ There is no real difference between numbers 123 and the letters abc. By for doing real math you need numbers as there is only a limited set of letters. If you only want to know what can be the result of stacksorting abc then take a piece of paper and try all possibilities. With three letters that can't be hard. $\endgroup$ – Hendrik Jan Nov 4 '14 at 22:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.