Generating combinations in parallel (Q1082084)

A parallel algorithm for generating all combinations of m out of n items in lexicographic order is presented. The algorithm uses m processors and runs in O(nCm) time. The cost of the algorithm, which is the parallel running time multiplied by the number of processors used, is optimal to within a constant multiplicative factor in view of the \(\Omega\) (nCm*m) lower bound on the number of operations required to solve this problem using a sequential computer.