TAOCP 2.2.1 Exercise 5
Let $p_1p_2\ldots p_n$ be a permutation of $1,2,\ldots,n$.
Section 2.2.1: Stacks, Queues, and Deques
Exercise 5. [M28] Show that it is possible to obtain a permutation $p_1 p_2 \ldots p_n$ from $12\ldots n$ using a stack if and only if there are no indices $i < j < k$ such that $p_j < p_k < p_i$.
Verified: no
Solve time: -
Setup
Let $p_1p_2\ldots p_n$ be a permutation of $1,2,\ldots,n$.
A permutation is said to be obtainable from $12\ldots n$ by a stack if there exists an admissible sequence of stack insertions and deletions such that the output sequence is $p_1p_2\ldots p_n$.
We must prove that such a permutation is obtainable if and only if there do not exist indices
$$ i<j<k $$
for which
$$ p_j<p_k<p_i. $$
Thus the forbidden pattern is a subsequence of three entries whose relative order is $3,1,2$.
Solution
First suppose that the permutation $p_1p_2\ldots p_n$ is obtainable by a stack. We shall show that no indices $i<j<k$ can satisfy
$$ p_j<p_k<p_i. $$
Assume the contrary. Let
$$ i<j<k,\qquad p_j<p_k<p_i. $$
Since $p_i$ appears before $p_j$ in the output, the element $p_i$ must be removed from the stack before $p_j$ is removed.
Because
$$ p_j<p_k<p_i, $$
the elements are inserted into the stack in the order
$$ p_j,\ p_k,\ p_i, $$
since the input is $1,2,\ldots,n$.
Consider the moment when $p_i$ is removed from the stack. At that time $p_j$ and $p_k$ have already been inserted, because both are smaller than $p_i$. Furthermore $p_j$ has not yet been removed, since it appears later in the output than $p_i$.
Hence $p_j$ is somewhere below $p_i$ in the stack. Since
$$ p_j<p_k<p_i, $$
the element $p_k$ was inserted after $p_j$ and before $p_i$. Therefore $p_k$ also lies above $p_j$ in the stack when $p_i$ is removed.
After $p_i$ is removed, the stack still contains $p_k$ above $p_j$. A stack removes items in last-in-first-out order, so $p_k$ must be removed before $p_j$. This contradicts the output order
$$ p_i,\ldots,p_j,\ldots,p_k, $$
in which $p_j$ precedes $p_k$.
Therefore no such indices $i<j<k$ exist.
For the converse, assume that the permutation contains no indices $i<j<k$ satisfying
$$ p_j<p_k<p_i. $$
We shall show that the permutation can be produced by a stack.
Process the desired output from left to right. To output $p_r$, insert into the stack all unused input elements up to and including $p_r$, then remove $p_r$ from the top of the stack.
This procedure is forced, since the input arrives in the order $1,2,\ldots,n$.
The only possible difficulty is that, when $p_r$ is to be output, some smaller element might lie above it in the stack. We prove that this cannot happen.
Suppose, to the contrary, that the procedure first fails when attempting to output $p_j$. Then some element $p_k$ lies above $p_j$ in the stack.
Since $p_k$ lies above $p_j$, it was inserted later, hence
$$ p_j<p_k. $$
Since the procedure has not previously failed, $p_k$ has not yet been output. Therefore $p_k$ occurs later in the permutation:
$$ j<k. $$
The element $p_k$ was inserted before the attempt to output $p_j$. Consequently the input has already reached $p_k$, so some earlier output value $p_i$ must satisfy
$$ p_i>p_k. $$
Choose $i$ to be the position at which an element at least as large as $p_k$ was first output. Then
$$ i<j<k, $$
and
$$ p_j<p_k<p_i. $$
This is precisely the forbidden configuration, contrary to hypothesis.
Hence the procedure never fails. Every required element appears on top of the stack when needed, and the permutation is generated successfully.
Therefore every permutation avoiding indices $i<j<k$ with
$$ p_j<p_k<p_i $$
is obtainable by a stack.
Combining the two directions proves the theorem.
This completes the proof.
∎
Verification
For necessity, the key fact is that if
$$ p_j<p_k<p_i, $$
then $p_j$ and $p_k$ must both have entered the stack before $p_i$ enters. Since $p_j$ enters first, $p_k$ remains above $p_j$ after $p_i$ is removed, forcing $p_k$ to leave before $p_j$, contrary to the output order.
For sufficiency, the constructive procedure inserts input elements until the next required output is available. Failure can occur only if a smaller desired element $p_j$ is trapped beneath a larger element $p_k$. Such a situation yields indices
$$ i<j<k,\qquad p_j<p_k<p_i, $$
where $p_i$ is an earlier output that caused $p_k$ to be inserted. Since the hypothesis excludes this pattern, no failure is possible.
Notes
The condition
$$ \text{there do not exist }i<j<k\text{ with }p_j<p_k<p_i $$
characterizes the stack permutations counted in Exercise 4. In modern terminology these are exactly the permutations avoiding the pattern $312$.