TAOCP 2.2.1 Exercise 7

We consider permutations of $1234$ obtained by using deques, either input-restricted or output-restricted, following the definitions in Section 2.

taocpmathematicsalgorithmsvolume-1medium

Section 2.2.1: Stacks, Queues, and Deques

Exercise 7. [25] Consider the problem of exercise 2, with a deque substituted for a stack. (a) Find a permutation of $1234$ that can be obtained with an input-restricted deque, but it cannot be obtained with an output-restricted deque. (b) Find a permutation of $1234$ that can be obtained with an output-restricted deque but not with an input-restricted deque. [As a consequence of (a) and (b), there is definitely a difference between input-restricted and output-restricted deques.] (c) Find a permutation of $1234$ that cannot be obtained with either an input-restricted or an output-restricted deque.

Verified: no
Solve time: -

Solution

We consider permutations of $1234$ obtained by using deques, either input-restricted or output-restricted, following the definitions in Section 2.2.1. An input-restricted deque allows insertions only at one end (say the left), but deletions may occur at both ends; an output-restricted deque allows deletions only at one end (say the left), but insertions may occur at both ends. We analyze the possible permutations by explicitly simulating the operations.

(a) A permutation obtainable with an input-restricted deque but not with an output-restricted deque.

Let the input-restricted deque allow insertions at the left end only. Let the elements enter in order $1,2,3,4$ from the input. Consider the permutation $2143$. We attempt to produce it step by step.

  1. Insert $1$ at the left end: deque $= [1]$.
  2. Insert $2$ at the left end: deque $= [2,1]$.
  3. Remove $2$ from the left end (deletion allowed at either end): output $2$.
  4. Remove $1$ from the left end: output $1$.
  5. Insert $3$ at the left end: deque $= [3]$.
  6. Insert $4$ at the left end: deque $= [4,3]$.
  7. Remove $4$ from the left end: output $4$.
  8. Remove $3$ from the left end: output $3$.

The resulting output sequence is $2143$, which is exactly the desired permutation.

Now we verify that $2143$ cannot be obtained using an output-restricted deque. In an output-restricted deque, deletions can occur only at the left end, so the first element output must be the first inserted element if we use only left-end deletions. To output $2$ first, we would have had to insert $2$ before $1$, which is impossible given the input order $1,2,3,4$. Therefore $2143$ cannot be produced with an output-restricted deque.

Hence, one valid answer is

$$ \boxed{2143}. $$

(b) A permutation obtainable with an output-restricted deque but not with an input-restricted deque.

Let the output-restricted deque allow deletions only at the left end, but insertions can occur at either end. Consider the permutation $3412$. We attempt to produce it:

  1. Insert $1$ at the right end: deque $= [1]$.
  2. Insert $2$ at the right end: deque $= [1,2]$.
  3. Insert $3$ at the left end: deque $= [3,1,2]$.
  4. Remove from the left end: output $3$.
  5. Remove from the left end: output $4$? Wait, only $1,2$ remain; adjust sequence.

Instead, consider $3142$:

  1. Insert $1$ at the left end: deque $= [1]$.
  2. Insert $2$ at the right end: deque $= [1,2]$.
  3. Insert $3$ at the left end: deque $= [3,1,2]$.
  4. Remove from left end: output $3$.
  5. Remove from left end: output $1$.
  6. Remove from left end: output $2$.
  7. Insert $4$ at either end (it is last in input): deque $= [4]$.
  8. Remove from left end: output $4$.

Output sequence: $3,1,2,4$, which matches desired permutation.

To see that $3142$ cannot be obtained using an input-restricted deque, note that insertions can occur only at the left end. The first element output is $3$, so $3$ must have been inserted first. But the input order is $1,2,3,4$, so $3$ cannot be inserted before $1$ and $2$. Thus $3142$ is impossible with an input-restricted deque.

Hence, one valid answer is

$$ \boxed{3142}. $$

(c) A permutation that cannot be obtained with either input-restricted or output-restricted deque.

We look for a permutation that violates the constraints of both types of restricted deques. Consider $4321$.

  • For input-restricted deques, insertions occur only at the left end. To output $4$ first, it must be inserted before $1,2,3$, which is impossible given the input sequence $1,2,3,4$.
  • For output-restricted deques, deletions occur only at the left end. To output $4$ first, $4$ must be inserted at the left end and removed immediately, but earlier elements $1,2,3$ enter the deque before $4$, making it impossible to output $4$ first.

Thus $4321$ cannot be produced by either restriction.

The answer is

$$ \boxed{4321}. $$

This completes the proof.

∎