Permuting with a stack

Revision en3, by Matjaz, 2017-04-19 10:43:34

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?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English Matjaz 2017-04-19 10:43:34 150 Clarified that input and output are not the same object.
en2 English Matjaz 2017-04-19 10:07:16 2 Tiny change: ' except $321$. \n\nBut' -> ' except $312$. \n\nBut'
en1 English Matjaz 2017-04-19 10:06:56 647 Initial revision (published)