Adaptive and Optimal Parallel Algorithms for Enumerating Permutations and Combinations

Three new adaptive and cost-optimal parallel algorithms are described for the problems of enumerating permutations and combinations ofm out ofn objects. The algorithms are designed to be executed on a very simple model of parallel computation which consists ofk autonomous processors running synchronously without needing to communicate among themselves. For the first two algorithms, 13$ k s$ N, where N is the number of permutations or combinations to be enumerated. When 1 ^ k < N/n, both algorithms require (H$N/k\. m) time for an optimal cost ofO(N.m). The third algorithm is designed for the case where m = n and 1 <*