A novel parallel algorithm for enumerating combinations

168. B. B. Zhou, R. P. Brent, X. Qu and W. Liang, A novel parallel algorithm for enumerating combinations, Proceedings of the 25th International Conference on Parallel Processing, Bloomingdale, Illinois, August 1996. IEEE Press, Vol. 2, 70-73.

Paper: dvi (11K), pdf (65K), ps (47K).


In this paper we propose a new algorithm for parallel enumeration of combinations of M out of N items. This algorithm uses N processing elements (or PEs). We prove that, if N and M are relatively prime, each PE will do the same operations and generate the same number of distinct combinations so that the computational load is well balanced. The algorithm has an important application in solving the problem of fault tolerance in replicated file systems.


Essentially the same algorithm was published earlier by Ivan Stojmenovic [Internat. J. of Computer Mathematics 42 (1992), 125-135]. We are grateful to Professor Stojmenovic for this information [personal communication, January 1997].

Go to next publication

Return to Richard Brent's index page