An optimal parallel algorithm for generating combinations

DOI10.1016/0020-0190(89)90192-0MaRDI QIDQ582077zbMATH OpenOpenAlexFDO

Authors Selim G. Akl, David Gries, Ivan Stojmenović

Publication date 1989

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(89)90192-0

zbMATH Keywords

concurrencydesign of algorithmsgenerating combinationsparallel algorithms

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Theory of operating systems (68N25) Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99)

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.

Recommendations

• A parallel algorithm for generating combinations
• Generating combinations in parallel
• scientific article; zbMATH DE number 4037239
• scientific article; zbMATH DE number 1302200
• scientific article; zbMATH DE number 4131653
• Parallel generation of permutations and combinations
• Spectral Analysis of an Oscillating Thermoviscoelastic Plate in a Transverse Magnetic Field
• Efficient massively parallel implementation of some combinatorial algorithms
• A Parallel Algorithm for Cost-Optimal Generation of Permutations ofrout ofnItems
• New methods for the generation of permutations, combinations, and other combinatorial objects in parallel

Cites work

• Adaptive and Optimal Parallel Algorithms for Enumerating Permutations and Combinations
• Adjacent interchange generation of combinations
• Generating combinations in parallel
• scientific article; zbMATH DE number 4155887 (Why is no real title available?)
• Parallel generation of permutations and combinations

Cited in

(16)

• Generating combinations in parallel
• Parallel generation of permutations and combinations
• A simple systolic algorithm for generating combinations in lexicographic order
• A systolic design for generating combinations in lexicographic order
• A parallel derangement generation algorithm
• A parallel algorithm for generating combinations
• A systolic generation of combinations
• New methods for the generation of permutations, combinations, and other combinatorial objects in parallel
• A new algorithm for generating combinations
• Listing combinatorial objects in parallel
• scientific article; zbMATH DE number 4106841 (Why is no real title available?)
• On random and adaptive parallel generation of combinatorial objects
• scientific article; zbMATH DE number 4195954 (Why is no real title available?)
• Parallel Processing and Applied Mathematics
• Parallel algorithms for generating combinatorial objects on linear processor arrays with reconfigurable bus systems.
• An optimal algorithm for generating equivalence relations on a linear array of processors

This page was built for publication: An optimal parallel algorithm for generating combinations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q582077)