Permuting with a stack

Правка en2, от Matjaz, 2017-04-19 10:07:16

Suppose we have an ordered sequence 1, 2, .., n.

We also have a stack. We will be using this stack to try to obtain different permutations of this sequence.

At any time we may either 1) push the front of our ordered sequence onto the stack or 2) pop the top of the stack and append it to our resulting permutation.

Which permutations of the original sequence can be obtained by such a process?

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

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский Matjaz 2017-04-19 10:43:34 150 Clarified that input and output are not the same object.
en2 Английский Matjaz 2017-04-19 10:07:16 2 Tiny change: ' except $321$. \n\nBut' -> ' except $312$. \n\nBut'
en1 Английский Matjaz 2017-04-19 10:06:56 647 Initial revision (published)