Combinatorics of Permutations, 2nd Edition

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