0
$\begingroup$

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

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\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, 2014 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, 2014 at 22:28

Your Answer

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

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