How to detect stack order?

Question

We take the sequence of integers from $1$ to $n$, and we push them onto a stack one by one in order. Between each push, we can choose to pop any number of items from the stack (from 0 to the current stack size).

Every time we pop a value from the stack, we will print it out.

For example, $1,2,3$ is printed out when we do push, pop, push, pop, push, pop. $3,2,1$ comes from push, push, push, pop, pop, pop.

However, $3,1,2$ is not a possible printout, because it is not possible to have $3$ printed followed by $1$, without seeing $2$ in between.

Question: How can we detect impossible orders like $3,1,2$?

In fact, based on my observation, I have come out a potential solution. But the problem is I can't prove my observation is complete.

The program that I wrote with the following logic:

When the current value minus the next value is larger than 1, a value between current and next cannot appear after next. For example, if current=3 and next=1, then the value between current (3) and next (1) is 2 which cannot appear after next(1), hence $3,1,2$ violates the rule.

Does this cover all cases?

Answer 1

I couldn't understand your approach exactly (Seems it's correct), but there is a simple rule for impossible orders: The order is impossible $iff$ there is $a_i,a_j,a_k$ such that $a_i > a_k > a_j$ and $i<j<k$. To such a $a_i,a_j,a_k$ we say bad triple.

Why? First you should prove that if there is bad triple then the sequence is impossible, but this is simple and I'll leave it as exercise (middle number couldn't pop sooner than bigger except smaller poped before all of them).

Second you should prove all impossible orders have at least one bad triple, Assume you have a sequence without any bad triple, you could find the order of push and pop so it's not impossible sequence. For reconstructing the push and pop orders just use naive approach (operation is pop while you iterating over consecutive numbers), but for formal proof (for simplicity) you could use induction, assume for all sequences of length $m$ if there isn't bad triple they aren't impossible. For sequence of length $n$, you can set operations as pop (start from end of sequence), while encountering with increasing consecutive numbers, now you have a sequence of length $m$, with $m < n$, without bad triple, so you can reconstruct push and pop for this sequence, so original one wasn't impossible. start of induction is sequence of length 3.