A Cost-Optimal Pipeline Algorithm for Permutation Generation in Lexicographic Order

In this paper we solve the open problem of designing a cost-optimal parallel algorithm for generating permutations ofMelements out of the set {0, 1, …,N− 1}, in lexicographic order. Our algorithm runs on the simplest model of parallel computation, i.e., a linear array of sizeM, where each processor PE(i) needs only a constant number of words of length logN, and is responsible for producing with constant delay, theith components in the successive permutations. This algorithm runs in timeO(N!/(N−M)!) on an array of sizeMand is therefore cost-optimal when the time needed to output the permutations is taken into account. Moreover, by doubling the number of cells, it is possible to implement this algorithm on a unidirectional linear array.