Can anyone please explain algorithm to generate the permutations possible when using only a single stack and push and pop are the only operations allowed. Have searched about it a lot, but no definite answer. Also the total number of such permutations is given by catalan numbers. But I fail to get a proof for that. Kindly explain that as well if possible.
Thanks!!
This problem uses an input queue and an output queue as well as a stack.
The operations are "push an item from the input queue onto the stack" and "pop an item from the stack onto the output queue".
1 2 3
output ______ ______ input
\ /
<--+ | +---
pop | | | push
| | v
stack
For example, with the input 1 2 3
, you can get the output 2 1 3
with the following sequence:
But you'll have a hard time if you try to generate 3 1 2
.
How do you generate all the permutations that are possible with these operations? Well, it's trivial to do recursively: in any given state (where the "state" consists of the contents of the input queue, the stack, and the output queue), there are at most two possible operations you can perform (you can push if there is at least one item on the input queue; you can pop if there is at least one item on the stack), which will give you at most two possible new states to explore.
For further detail regarding this problem, and the relationship with Catalan numbers, go and find a copy of Knuth's "The Art of Computer Programming", volume 1 (3rd ed.) - it's discussed in §2.2.1; see exercises 2 - 5 on pp. 242-243 (and a better version of my diagram on p. 240!).