A permutation network is a circuit that is hard wired to effect a particular permutation of its input. It takes n inputs and produces n outputs. An example of a permutation network for n = 4 is shown...

A permutation network is a circuit that is hard wired to effect a particular permutation of its input. It takes n inputs and produces n outputs. An example of a permutation network for n = 4 is shown in Fig. 6.3. For input (1 2 3 4) the network produces (2 4 1 3). Feeding (24 1 3) back into the network (using the dotted lines) yields (4 3 2 1). Repeating the process yields (3 14 2) and then (1 2 3 4), that is, the original permutation. This means that the network in Fig. 6.3 is capable of producing only four of the twenty-four permutations of four items. Can you design a network capable of generating all permutations?