Adaptive and Optimal Parallel Algorithms for Enumerating Permutations and Combinations
Selim G. Akl · The Computer Journal · 1987
Three new adaptive and cost-optimal parallel algorithms are described for the problems of enumerating permutations and combinations of m out of n objects. The algorithms are designed to be executed on a very simple model of parallel computation which consists of k autonomous processors running synchronously without needing to communicate among themselves. For the first two algorithms, I ≤ k ≤ N, where N is the number of permutations or combinations to be enumerated. When I ≤ k ≤ N/n, both algorithms require 0([N/k]· m) time for an optimal cost of 0(N.m). The third algorithm is designed for the case where m = n and I ≤ k ≤ n. It runs in 0([n!/k] · m) time for an optimal cost of 0(n!.n).