
Get Them All. Algorithms and Permutations. 333
After Steps 3−4
After Steps 1−2
Start
End
1234
3412
2
1
1
2
4
3
43
Output Deque Input
After Steps 5−6
FIGURE 8.6
Obtaining p = 3412 by a deque.
into the output.
Example 8.32
The permutation 3412 is deque obtainable. See Figure 8.6 for a movement
sequence leading to this permutation.
In order to have an equivalent of Proposition 8.31, we need to define when
we call a permutation general deque-sortable,orgd-sortable,andwhatthe
gd-sorting algorithm is. As the general deque is more flexible a tool than
the stack, we can allow more flexibility in the deque sorting algorithm than
in the stack sorting algorithm. That is, our