Equivalence of input-restricted and output-restricted deques

Question

There is a question in Art of Computer Programming by Knuth which needs us to prove that Input restricted deques and Output restricted deques can form the same number of (and possibly individually same) permutations. The solution is

By operating backwards, we can get the reverse of the inverse of the reverse of any input-restricted permutation with an output-restricted deque, and conversely. This rule sets up a one-to-one correspondence between the two sets of permutations.

Which doesn't seem very clear. Can someone explain the answer in english?

Answer 1

Let's consider permutations on the first $n$ natural numbers (excluding $0$). By $D_F$ we denote a deletion at the front end and by $D_B$ a deletion at the back of some deque. Similarly, by $I_f$ and $I_B$ we denote insertion at the front and the back of some deque respectively.

Assume now that $P$ is some permutation which can be formed with an output-restricted deque. This means that there is some sequence $T$ of (wlog) front deletions $D_F$, front insertions $I_F$ and back insertions $I_B$ which transforms the sequence of numbers $1, 2, ..., n$ into $P$.

Now we transform $T$ in the following way. We replace every $D_F$ by $I_F$, every $I_F$ by $D_F$ and every $I_B$ by $D_B$. In this way we obtain a sequence of operations $T'$. Let $S$ be the sequence obtained by reversing $T'$.

Now observe that $T'$ and thus also $S$ contain insertions at only one end. Thus $S$ can be executed on an input-restricted deque. Furthermore we observe that executing $S$ on the permutation $P$ will give us the sequence $1, 2, ..., n$ again. In other words, executing $S$ on $1, 2, ..., n$ will give us the inverse permutation of $P$.

We can make the same argument starting with an input-restricted deque. Thus we have established a one-to-one correspondence.

Note that I use an input-restricted deque which can only handle insertions at the front and I use an output-restricted deque which can only handle deletions at the front. In this way I think we get rid of one of the 'reverse' thingies in the books explanation. In other words, my argument only gives you one reversion and one inversion because of my choice of deques.