TAOCP 2.2.1 Exercise 8

Section 2.2.1: Stacks, Queues, and Deques

Exercise 8. [22] Are there any permutations of $12\ldots n$ that cannot be obtained with the use of a deque that is neither input- nor output-restricted?

Verified: no
Solve time: -

Solution

Let $p = p_1 p_2 \ldots p_n$ be a permutation of $12\ldots n$, and let $D$ be a deque that is neither input- nor output-restricted. We wish to determine whether there exists a permutation that cannot be obtained using $D$.

By definition, a deque allows insertions and deletions at both ends. Consider the standard input sequence $12\ldots n$, and let us construct $p$ step by step. At each stage, the next element of the input can be placed at either end of $D$, and at any stage, either end of $D$ can output an element. Therefore, the deque can simulate both a stack and a queue simultaneously.

We examine the constraints imposed by stacks and queues on obtainable permutations. A stack cannot produce permutations containing the forbidden subsequence $p_j < p_k < p_i$ for $i < j < k$ (by exercise [5]), and a queue can only produce the identity permutation $12\ldots n$ (by exercise [6]). The deque generalizes both: we may temporarily store elements in either end, giving complete freedom in rearranging the sequence.

To show that any permutation $p$ can be obtained with a deque, proceed as follows. Initialize $D$ as empty. Consider the elements of $p$ in order:

1. If the next desired element $p_i$ is at the front or rear of $D$, output it immediately.
2. Otherwise, move elements from the input $12\ldots n$ into $D$, choosing the end opposite to the one from which we will eventually output $p_i$, until $p_i$ reaches an end of $D$. Output $p_i$.

Since $D$ has two ends, it is always possible to position any remaining input element at either end without violating previous outputs. This process can be repeated inductively: after outputting $p_1, \ldots, p_{i-1}$, the next element $p_i$ can be placed at an end of $D$ by suitable insertions from the input. No element is ever "trapped" in the middle of $D$, because both ends are available for insertions and deletions.

Formally, define an invariant: after outputting $p_1, \ldots, p_{i-1}$, all remaining elements of the input and $D$ can be rearranged to bring $p_i$ to an end. The algorithm above maintains this invariant: insert $p_i$ from the input at the end opposite to where it will be output, output $p_i$, and repeat. By induction on $i$, every element of $p$ can be produced.

Therefore, there are no permutations of $12\ldots n$ that are unobtainable using a deque that is neither input- nor output-restricted. Every permutation can be obtained by suitable sequences of insertions and deletions at the two ends.

The final answer is:

$$ \boxed{\text{No; every permutation can be obtained.}} $$

This completes the proof.

∎