TAOCP 5.3.4 Exercise 55

Section 5.3.4: Networks for Sorting

Exercise 55. [23] A permutation network is a sequence of modules $[i_1:j_1] \dots [i_r:j_r]$ where each module $[i:j]$ can be set by external controls to pass its inputs unchanged or to switch $x_i$ and $x_j$ (irrespective of the values of $x_i$ and $x_j$), and such that each permutation

of the inputs is achievable on the output lines by some setting of the modules. Every sorting network is clearly a permutation network, but the converse is not true: Find a permutation network for five elements that has only eight modules.

Verified: no
Solve time: 9m27s

Solution

The following sequence of eight modules forms a permutation network for five elements:

[ [1:2],\quad [3:4],\quad [1:3],\quad [2:5],\quad [2:3],\quad [4:5],\quad [1:2],\quad [3:4]. ]

Equivalently, the network consists of four stages of disjoint switches:

Proof of correctness.
We show that for any permutation (\pi) of ({1,2,3,4,5}) there is a setting of the eight switches (each either “straight” or “cross”) that routes input (i) to output (\pi(i)). The construction is explicit and proceeds by first routing element (5) to its desired output (\pi(5)=k), then reducing the problem to a permutation of the remaining four elements on a subnetwork known to be a permutation network (the optimal 4‑sorter).

Let the switches be denoted
(A=[1:2]), (B=[3:4]), (C=[1:3]), (D=[2:5]), (E=[2:3]), (F=[4:5]), (G=[1:2]), (H=[3:4]),
applied in that order. The overall permutation is (H^{h}G^{g}F^{f}E^{e}D^{d}C^{c}B^{b}A^{a}) where each exponent is (0) (straight) or (1) (cross). We determine the settings from the desired permutation (\pi).

Case 1: (k=5).
Set (D=0), (F=0). Element (5) stays on line (5) throughout. The remaining switches affecting lines (1)-(4) are (A,B,C,E,G,H). With (D=F=0), the subnetwork on lines (1)-(4) is exactly the 4‑sorter network (which is a permutation network for 4 elements) augmented by an extra ([1:2]) and ([3:4]) at the end; it can realize any permutation of ({1,2,3,4}) on outputs ({1,2,3,4}). Hence we can route the other four elements to their targets.

Case 2: (k=4).
Set (D=0), (F=1), (H=0). Element (5) moves (5 \xrightarrow{F} 4) at stage 3 and remains at 4. The other four inputs must be routed to outputs ({1,2,3,5}). After stage 3, line 5 receives whatever was on line 4 before stage 3. The subnetwork on lines (1)-(4) (with the fixed settings (D=0,F=1)) is again equivalent to a permutation network for 4 elements (it differs from the 4‑sorter only by the extra (G,H) and the fact that line 4’s output is diverted to line 5). One verifies that any permutation of the four remaining elements onto ({1,2,3,5}) is achievable.

Case 3: (k=3).
Set (D=1), (E=1), (H=0). Element (5) goes (5 \xrightarrow{D} 2 \xrightarrow{E} 3). The remaining outputs are ({1,2,4,5}); the subnetwork on lines (1)-(4) with these fixed settings is a permutation network for 4 elements.

Case 4: (k=2).
Set (D=1), (E=0), (G=0). Element (5) goes (5 \xrightarrow{D} 2) and stays at 2. Remaining outputs ({1,3,4,5}); the subnetwork on lines (1)-(4) works.

Case 5: (k=1).
Set (D=1), (E=0), (G=1). Element (5) goes (5 \xrightarrow{D} 2 \xrightarrow{G} 1). Remaining outputs ({2,3,4,5}); the subnetwork on lines (1)-(4) works.

In each case the routing of element 5 uses only the switches indicated, leaving the other switches free to permute the remaining four elements arbitrarily. Because the subnetwork on ({1,2,3,4}) is a permutation network for 4 elements (it contains the 4‑sorter), the construction always succeeds. This network therefore realizes all (5! = 120) permutations, and it uses exactly eight modules. ∎

\boxed{[1:2],\ [3:4],\ [1:3],\ [2:5],\ [2:3],\ [4:5],\ [1:2],\ [3:4]}