## 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).

## Abstract

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.
## Comments

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