TAOCP 2.2.1 Exercise 2

We are asked to determine whether the permutations $325641$ and $154623$ of six railroad cars numbered $1,2,3,4,5,6$ can be obtained using a single stack in the manner of Fig.

taocpmathematicsalgorithmsvolume-1simple

Section 2.2.1: Stacks, Queues, and Deques

Exercise 2. [15] Imagine four railroad cars positioned on the input side of the track in Fig. 1, numbered $1$, $2$, $3$, and $4$, from left to right. Suppose we perform the following sequence of operations (which is compatible with the direction of the arrows in the diagram and does not require cars to "jump over" other cars): (i) move car $1$ into the stack; (ii) move car $2$ into the stack; (iii) move car $2$ into the output; (iv) move car $3$ into the stack; (v) move car $4$ into the stack; (vi) move car $4$ into the output; (vii) move car $3$ into the output; (viii) move car $1$ into the output.

As a result of these operations the original order of the cars, $1234$, has been changed into $2431$. It is the purpose of this exercise and the following exercises to examine what permutations are obtainable in such a manner from stacks, queues, or deques.

If there are six railroad cars numbered $123456$, can they be permuted into the order $325641$? Can they be permuted into the order $154623$? (In case it is possible, show how to do it.)

Verified: yes
Solve time: 32s

Solution

We are asked to determine whether the permutations $325641$ and $154623$ of six railroad cars numbered $1,2,3,4,5,6$ can be obtained using a single stack in the manner of Fig. 1, where cars may enter the stack from the input track and leave the stack in last-in-first-out (LIFO) order. Let us analyze each case systematically.

Case 1: Target permutation $325641$

Let the input sequence be $1,2,3,4,5,6$ from left to right. Denote the stack at any moment by $S$, with the top at the right. We attempt to produce the output sequence $3,2,5,6,4,1$.

We proceed step by step:

  1. Output $3$ first: The first car in the input is $1$, which cannot go directly to output. Move $1 \Leftarrow S$; stack $S = [1]$. Next, input car $2$, move $2 \Leftarrow S$; stack $S = [1,2]$. Next, input car $3$, move $3 \Leftarrow S$; stack $S = [1,2,3]$. Now $3$ is on top, so we can output $3$: $x \Leftarrow S$ gives $x=3$, stack $S = [1,2]$.
  2. Output $2$ next: Top of $S$ is $2$, so $2 \Leftarrow S$ gives $x=2$, stack $S = [1]$.
  3. Output $5$ next: Input next car is $4$, which must enter the stack: $4 \Leftarrow S$, stack $S = [1,4]$. Next input car is $5$, move $5 \Leftarrow S$, stack $S = [1,4,5]$. Top of $S$ is $5$, so output $5$: $x \Leftarrow S$ gives $x=5$, stack $S = [1,4]$.
  4. Output $6$ next: Input next car is $6$, move $6 \Leftarrow S$, stack $S = [1,4,6]$. Top is $6$, output $6$: $x \Leftarrow S$ gives $x=6$, stack $S = [1,4]$.
  5. Output $4$ next: Top of $S$ is $4$, output $4$: $x \Leftarrow S$ gives $x=4$, stack $S = [1]$.
  6. Output $1$ last: Top of $S$ is $1$, output $1$: $x \Leftarrow S$ gives $x=1$, stack $S = [,]$.

All steps are compatible with LIFO order. Therefore, permutation $325641$ can be obtained.

A valid sequence of operations is:

$$ \begin{aligned} &1 \Leftarrow S, \quad 2 \Leftarrow S, \quad 3 \Leftarrow S, \quad x \Leftarrow S ; (3), \ &x \Leftarrow S ; (2), \quad 4 \Leftarrow S, \quad 5 \Leftarrow S, \quad x \Leftarrow S ; (5), \ &6 \Leftarrow S, \quad x \Leftarrow S ; (6), \quad x \Leftarrow S ; (4), \quad x \Leftarrow S ; (1). \end{aligned} $$

Case 2: Target permutation $154623$

We attempt to output sequence $1,5,4,6,2,3$ from input $1,2,3,4,5,6$.

  1. Output $1$ first: Input car $1$ is directly output, no stack needed.
  2. Output $5$ next: Input sequence has $2,3,4,5,6$ remaining. To output $5$ next, we must first place $2,3,4 \Leftarrow S$, so $S = [2,3,4]$. Input car $5$ can then be output immediately: $x=5$.
  3. Output $4$ next: Top of $S$ is $4$, output $4$: $S = [2,3]$.
  4. Output $6$ next: Next input car is $6$, output $6$ immediately.
  5. Output $2$ next: Top of $S$ is $3$, but we need $2$ next. The LIFO order of stack prevents accessing $2$ without first removing $3$, which would require outputting $3$ before $2$. This violates the desired output order.

Thus, the stack cannot produce permutation $154623$ because the order $2$ after $6$ is impossible while preserving LIFO constraints.

Conclusion

Permutation $325641$ can be obtained by a single stack. Permutation $154623$ cannot be obtained by a single stack.

$$ \boxed{325641\text{ is possible, }154623\text{ is impossible}} $$

This completes the proof.

∎