TAOCP 2.2.1 Exercise 10

We are asked to define the concept of an _admissible_ sequence of the symbols $S$, $Q$, and $X$ for an output-restricted deque, in such a way that every permutation of $n$ elements obtainable with the...

taocpmathematicsalgorithmsvolume-1math-medium

Section 2.2.1: Stacks, Queues, and Deques

Exercise 10. [M25] (See exercise 3.) Let S, Q, and X denote respectively the operations of inserting an element at the left, inserting an element at the right, and emitting an element from the left, of an output-restricted deque. For example, the sequence QQXSXSXX will transform the input sequence 1234 into 1342. The sequence SXQSXSXX gives the same transformation.

Find a way to define the concept of an admissible sequence of the symbols S, Q, and X, so that the following property holds: Every permutation of $n$ elements that is attainable with an output-restricted deque corresponds to precisely one admissible sequence.

Verified: no
Solve time: -

Solution

We are asked to define the concept of an admissible sequence of the symbols $S$, $Q$, and $X$ for an output-restricted deque, in such a way that every permutation of $n$ elements obtainable with the deque corresponds to exactly one admissible sequence. Let the input sequence be $1,2,\dots,n$.

An output-restricted deque allows insertions at both ends but deletion only at the left end. Thus the allowed operations are:

  • $S$: insert at the left,
  • $Q$: insert at the right,
  • $X$: delete (emit) from the left.

Let $a_1 a_2 \dots a_m$ be a sequence of operations on an initially empty deque. We define admissibility by the following rules:

  1. Matching deletions: At any point in the sequence, the number of $X$ operations cannot exceed the total number of insertions ($S$ and $Q$) performed so far. That is, for each prefix of length $k$ of the sequence, if $n_X(k)$ is the number of $X$ operations and $n_{S+Q}(k)$ is the number of $S$ and $Q$ operations, then

$$ n_X(k) \le n_{S+Q}(k). $$ 2. Input correspondence: Each input element is inserted exactly once, either via $S$ or $Q$, and is eventually emitted exactly once via $X$. 3. Left-first deletion constraint: Whenever an $X$ occurs, it must correspond to the element at the left end of the deque at that time. This uniquely determines which element is emitted given the current content of the deque. 4. Uniqueness of sequence: No two consecutive admissible sequences can produce the same permutation if the sequence of $S$ and $Q$ operations is identical, because each deletion $X$ removes the leftmost element at that point. Consequently, for any given output permutation, there is exactly one admissible sequence of operations $S$, $Q$, $X$ that produces it.

We may formalize this in terms of generation rules:

  • Let $L$ be the current deque content.
  • At any step, if $L$ is empty, only $S$ or $Q$ may occur. If $L$ is nonempty, $S$, $Q$, or $X$ may occur.
  • Each element of the input sequence is inserted once and only once; each element of the output sequence is deleted once and only once.
  • An $X$ operation always removes the leftmost element of $L$.

Illustration: Consider the example sequence $1234 \xrightarrow{QQXSXSXX} 1342$. Let us check its admissibility:

  1. Initial input: $1$ (next input element).
  2. $Q$: insert $1$ at right. Deque $[1]$.
  3. $Q$: insert $2$ at right. Deque $[1,2]$.
  4. $X$: delete leftmost → emit $1$. Output sequence so far $1$. Deque $[2]$.
  5. $S$: insert $3$ at left. Deque $[3,2]$.
  6. $X$: delete leftmost → emit $3$. Output $13$. Deque $[2]$.
  7. $S$: insert $4$ at left. Deque $[4,2]$.
  8. $X$: delete leftmost → emit $4$. Output $134$. Deque $[2]$.
  9. $X$: delete leftmost → emit $2$. Output $1342$. Deque empty.

At every step, the number of $X$ operations never exceeds the number of insertions, each input element is inserted once and emitted once, and the deletions always occur at the left. Therefore the sequence is admissible.

Consequences:

  • Rule 1 ensures that the deque never underflows.
  • Rules 2 and 3 enforce that each permutation is produced in a unique way.
  • Rule 4 guarantees a one-to-one correspondence between admissible sequences and attainable permutations.

Thus an admissible sequence of $S$, $Q$, and $X$ for an output-restricted deque is any sequence satisfying:

  1. The number of $X$ operations never exceeds the number of preceding insertions.
  2. Each input element is inserted exactly once and emitted exactly once.
  3. Each $X$ removes the leftmost element currently in the deque.

This definition achieves the required property: every permutation of $n$ elements obtainable with an output-restricted deque corresponds to exactly one admissible sequence.

This completes the proof.

∎