TAOCP 2.2.1 Exercise 3

Section 2.2.1: Stacks, Queues, and Deques

Exercise 3. [25] The operations (i) through (viii) in the previous exercise can be much more concisely described by the code SSXSSXXX, where S stands for "move a car from the input into the stack," and X stands for "move a car from the stack into the output." Some sequences of S's and X's specify meaningless operations, since there may be no cars available on the specified track; for example, the sequence SXXSSXXS cannot be carried out, since we assume that the stack is initially empty.

Let us call a sequence of S's and X's admissible if it contains $n$ S's and $n$ X's, and if it specifies no operations that cannot be performed. Formulate a rule by which it is easy to distinguish between admissible and inadmissible sequences; show furthermore that no two different admissible sequences give the same output permutation.

Verified: no
Solve time: -

Solution

Let a sequence consist of the symbols S and X, where S means "move the next car from the input into the stack" and X means "move the top car from the stack into the output."

A sequence is admissible when it contains $n$ occurrences of S, $n$ occurrences of X, and every operation can actually be performed.

Suppose that, in reading the sequence from left to right, a certain initial segment contains $s$ symbols S and $x$ symbols X. After these operations have been carried out, exactly $s-x$ cars are in the stack, since each S inserts one car and each X removes one car.

The stack can never contain a negative number of cars. Therefore every initial segment of an admissible sequence must satisfy

$$ s-x\ge0, $$

or equivalently,

$$ x\le s. \tag{1} $$

Furthermore, the sequence must contain exactly $n$ symbols S and exactly $n$ symbols X.

Conversely, assume that a sequence contains $n$ symbols S$ and $n$ symbols X, and that condition (1) holds for every initial segment. After any initial segment there are $s-x\ge0$ cars in the stack, hence no operation Xis ever requested when the stack is empty. Also, at most $n$ symbolsSoccur, so there is always an unused input car whenever anS` is performed before all $n$ insertions have taken place. Therefore every indicated operation can be carried out.

Hence the rule is:

A sequence is admissible if and only if it contains equally many S's and X's, and in every initial segment the number of X's does not exceed the number of S's.

Now consider two admissible sequences. We shall show that different admissible sequences cannot produce the same output permutation.

Let $A$ and $B$ be two admissible sequences that produce the same permutation. Assume $A\ne B$. Let $k$ be the first position at which they differ. Up to position $k-1$ the two sequences perform exactly the same operations, so they have reached the same stack contents, the same input position, and the same output already produced.

At position $k$, one sequence must contain S and the other X. Without loss of generality, let $A$ contain S and $B$ contain X.

Immediately before position $k$, suppose the next unused input car is numbered $m$. Sequence $A$ places car $m$ onto the stack. Sequence $B$ removes the current top car of the stack and sends it to the output. Since car $m$ has not yet entered the stack in sequence $B$, the car output by $B$ is different from $m$.

From this point onward, sequence $A$ can never output any car before car $m$ enters the stack, because $m$ has already entered at step $k$. Sequence $B$ has already output a different car at step $k$. Therefore the next output symbol produced by the two computations is different. The resulting output permutations cannot be identical.

This contradicts the assumption that $A$ and $B$ produce the same permutation. Hence two distinct admissible sequences cannot yield the same output permutation.

Therefore:

$$ \boxed{\text{An admissible sequence is one for which every initial segment contains at least as many }S\text{'s as }X\text{'s, and the total numbers of }S\text{'s and }X\text{'s are equal.}} $$

and

$$ \boxed{\text{No two different admissible sequences produce the same output permutation.}} $$

∎