An optimal parallel algorithm for generating combinations (Q582077)

We present a parallel algorithm for generating in lexicographically ascending order the C(m,n) combinations of m objects chosen from 1..n, where \(1\leq m<n\) and C(m,n) is the total number of combinations. (Henceforth, we write C(m,n) as Cmn.) We call these combinations m- combinations. The algorithm is designed to run on a linear array of m processors, where each processor communicates only with its (left and right) neighbors, each has constant size memory, and each is responsible for producing one element of each combination. A combination takes constant time to produce from the preceding one, so the algorithm requires time 0(Cmn). This improves over previous algorithms in three respects: it runs on a weaker model, it is cost optimal (assuming the time to output the combinations is counted), and it requires the calculation of no integer greater than n.