A Cost-Optimal Pipeline Algorithm for Permutation Generation in Lexicographic Order
✍ Scribed by Clémentin Tayou Djamegni; Maurice Tchuenté
- Publisher
- Elsevier Science
- Year
- 1997
- Tongue
- English
- Weight
- 142 KB
- Volume
- 44
- Category
- Article
- ISSN
- 0743-7315
No coin nor oath required. For personal study only.
✦ Synopsis
In this paper we solve the open problem of designing a costoptimal parallel algorithm for generating permutations of M elements 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 size 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 runs in time O(N!/(N -M)!) on an array of size M and 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.