© 1989 by British Computer Society
Generating Permutations on a VLSI Suitable Linear Network
LIP-IMAG, Ecole Normale Supérieure de Lyon, 46, allée d'ltalie, 69364 Lyon Cedex 07, France
Received 1 December 1987; revised 1 January 1989
A parallel algorithm for generating all the k! permutations of kPk for every (1 
k n) is presented. The architecture consists of a linear processor array with n elements. The kth processor receives a permutation p of k–1Pk–1 from the (k — 1 )th processor and intercalates k at all the k possible positions of the sequence p, one at a time. After each intercalation it sends the permutation obtained to the (k + l)th processor and also outputs it. In this way the nth processor outputs all the n! permutations of nPn in (n + n!) units of time and our profit are all the kPk(1 k < N) which output is included in that time. The network is VLSI implementable and fault tolerant. It is shown how to find the position of a given permutation and how to obtain the permutation of a given position, where position refers to the generation order of the permutations by each processor. With a simple modification in the algorithm performed by the processors, the network is able to generate combinations.