An optimal parallel algorithm for generating combinations
type: Item
instance of: scholarly article
title: An optimal parallel algorithm for generating combinations
zbMATH Open document ID: 0689.68043
DOI: 10.1016/0020-0190(89)90192-0
author: Selim G. Akl
author: David Gries
author: Ivan Stojmenović
published in: Information Processing Letters
publication date: 1989-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68R99
Mathematics Subject Classification ID: 05A15
Mathematics Subject Classification ID: 68N25
zbMATH DE Number: 4129995
zbMATH Keywords: concurrency
zbMATH Keywords: design of algorithms
zbMATH Keywords: parallel algorithms
zbMATH Keywords: generating combinations
MaRDI profile type: Publication
full work available at URL: 0020-0190(89)90192-0
OpenAlex ID: W2045504543
cites work: Adaptive and Optimal Parallel Algorithms for Enumerating Permutations and Combinations
cites work: Q3484355
cites work: Generating combinations in parallel
cites work: Parallel generation of permutations and combinations
cites work: Adjacent interchange generation of combinations
Recommended article: A parallel algorithm for generating combinations
Recommended article: Generating combinations in parallel
Recommended article: Q3776653
Recommended article: Q4247467
Recommended article: Q3033316
Recommended article: Parallel generation of permutations and combinations
Recommended article: Spectral Analysis of an Oscillating Thermoviscoelastic Plate in a Transverse Magnetic Field
Recommended article: Efficient massively parallel implementation of some combinatorial algorithms
Recommended article: A Parallel Algorithm for Cost-Optimal Generation of Permutations ofrout ofnItems
Recommended article: New methods for the generation of permutations, combinations, and other combinatorial objects in parallel
description: scientific article; zbMATH DE number 4129995