Ct. Djamegni et M. Tchuente, A COST-OPTIMAL PIPELINE ALGORITHM FOR PERMUTATION GENERATION IN LEXICOGRAPHIC ORDER, Journal of parallel and distributed computing, 44(2), 1997, pp. 153-159
Citations number
7
Categorie Soggetti
Computer Sciences","Computer Science Theory & Methods
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.