Codeforces and Polygon may be unavailable from December 6, 19:00 (UTC) to December 6, 21:00 (UTC) due to technical maintenance. ×

Matjaz's blog

By Matjaz, history, 8 years ago, In English

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?

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Matjaz (previous revision, new revision, compare).

»
8 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Matjaz (previous revision, new revision, compare).

»
8 years ago, # |
Rev. 3   Vote: I like it +16 Vote: I do not like it

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.