Suppose we have an ordered (input) queue containing 1, 2, .., n.
We also have a stack and an "output queue". We will be using this stack to try to obtain different permutations of this sequence in the "output queue".
At any time we may either 1) push the front of the input queue onto the stack or 2) pop the top of the stack and push it to the "output queue".
Which permutations of the original sequence can be obtained by such a process in the "output queue"?
(I ask because many programming puzzles seem to be built around this question).
So for example if the starting sequence is 1, 2, 3 we can obtain all permutations except 312.
But what is the answer in general?
Auto comment: topic has been updated by Matjaz (previous revision, new revision, compare).
Why do you think we cannot obtain 312? You should get it by doing push pop push pop.
You can rotate the sequence by doing push pop, and you can swap two consecutive elements by rotating them to the front and then doing push push pop pop. That alone is enough to produce any order.
Ah I guess I wasn't clear when I wrote this — the input and the output are not the same object. The stack is picking up elements from one sequence/array/queue and depositing them in a different sequence/array/queue.
So "push pop push pop" produces "12" in the "output queue", an empty stack and a "3" remaining in the "original queue".
Auto comment: topic has been updated by Matjaz (previous revision, new revision, compare).
The valid sequences would be like this :
Starting from X=0, In each step you can have a big jump forward (from X to some X+P where P is positive and of course you haven't seen X+P before). Or you can have one unit jump backward (from X to the biggest number less than X that you haven't seen yet).
For example you can't reach 312 cause when X=3 you can't jump backward into 1, before seeing 2.