Consider the sorting networks described in chapter 4. These networks can be used as permutation generators as follows. Let S = {1, 2, 3,4, 5} and assume that we wish to generate the permutation...

Consider the sorting networks described in chapter 4. These networks can be used as permutation generators as follows. Let S = {1, 2, 3,4, 5} and assume that we wish to generate the permutation (5 3 2 1 4) from the initial permutation (1 2 3 4 5). We begin by assigning each integer in the initial permutation an index (or subscript) indicating its position in the desired permutation. This gives (14 23 32 45 5,). The sequence of indices can now be sorted on a sorting network: When two indices are to be swapped, each carries its associated integer along. The result is (5, 32 2, 14 45) as required. For a given n, can all n! permutations be generated in this fashion? Would they be in lexicographic order? Analyze the running time, number of processors, and cost of your algorithm.