A COST-OPTIMAL PIPELINE ALGORITHM FOR PERMUTATION GENERATION IN LEXICOGRAPHIC ORDER

In this paper we solve the open problem of designing a cost-optimal pa rallel algorithm for generating permutations of M elements out of the set {0, 1,..., N - 1}, in lexicographic order. Our algorithm runs on t he simplest model of parallel computation, i.e., a linear array of siz e M, where each processor PE(i) needs only a constant number of words of length log N, and is responsible for producing with constant delay, the ith components in the successive permutations. This algorithm run s in time O(N!/(N-M)!) on an array of size M and is therefore cost-opt imal when the time needed to output the permutations is taken into acc ount. Moreover, by doubling the number of cells, it is possible to imp lement this algorithm on a unidirectional linear array. (C) 1997 Acade mic Press.