An optimal parallel algorithm for generating combinations

An algorithm is presented for generating, in lexicographically ascending order, the C(m, n) combinations of m objects chosen from 1..n, where one is less than or equal to m, m is less than n, and C(m, n) is the total number of combinations. These combinations are called m-combinations. The algorithm...

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 1989-11, Vol.33 (3), p.135-139
Main Authors: Akl, Selim G., Gries, David, Stojmenovic, Ivan
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Algorithms
Applied sciences
Computer science
Computer science
control theory
systems
Concurrency
design of algorithms
Exact sciences and technology
generating combinations
Information processing
Mathematical models
parallel algorithms
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:An algorithm is presented for generating, in lexicographically ascending order, the C(m, n) combinations of m objects chosen from 1..n, where one is less than or equal to m, m is less than n, and C(m, n) is the total number of combinations. These combinations are called m-combinations. The algorithm is designed to run on a linear array of m processors, where each processor: 1. communicates only with its left and right neighbors, 2. has constant size memory, and 3. is responsible for producing one element of each combination. Because a combination takes constant time to produce from the preceding one, the algorithm requires time O(Cmn). This improves over previous algorithms in 3 respects: 1. It runs on a weaker model. 2. It is cost optimal - assuming the time to output the combinations is counted. 3. It requires the calculation of no integer greater than n.
ISSN:0020-0190
1872-6119
DOI:10.1016/0020-0190(89)90192-0