Sequential Permutation Networks

Two sequential permutation networks which generate all nǃ permutations without duplication are presented. Each permutation can be derived from its predecessor autonomously in one clock step. Based on the principle of recursive execution of a product of transpositions, the first network is constructed in multiple cascades of ½(n^²-n) switching elements each of which permutes its input pair to its output pair according to its internal state, and is controlled sequentially by the same principle. Next, the network whose structure and control sequence are complementary to those of the first is presented. The first is named a cyclic permutation network and is an explicit representation of a mapping function The second is named a lexicographic permutation network and is an explicit representation of a factorial counting function where ah is a h-nary factorial digit 0 ≤ ah ≤ (n-1). The characteristics of the networks are investigated by establishing a one-to-one correspondence among nI integers, n! permutations, and n! states of the networks. For the lexicographic permutation network which can generate all permutations in lexicographic order, three examples of applications are given.