Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Parallel generation of permutations and combinations
Chen G., Chern M. BIT26 (3):277-283,1986.Type:Article
Date Reviewed: Jul 1 1988

Given n objects, (1,2, . . . ,n), and m≤9Tn processors connected in a logical ring, an algorithm is given for generating permutations of length k ≤9Tm or less. It is shown that the quotient of the sequential and parallel time complexities is O(m). Thus, a maximum speedup is attained. A divide-and-conquer approach is used where the responsibility for generating specific subsets of permutations is meted out based on the value of the leading object. Responsibility for subsequences is assigned in the same way, and such subsequences are shared by shifting components (with modification) around the ring. The authors show how to extend the algorithm from rings to arrays of processors.

This paper would be of interest to someone in search of a concise example of the divide-and-conquer paradigm. It might be of interest to those seeking parallel heuristic solutions to the knapsack or other combinatorial programming problems. While the text is complicated by the use of nonstandard phrases that describe standard algorithmic steps (e.g., the manipulation of stacks), an excellent example is presented that dissolves the ambiguity.

Reviewer:  B. P. Buckles Review #: CR111553
Bookmark and Share
 
Combinatorics (G.2.1 )
 
 
Parallelism And Concurrency (F.1.2 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Combinatorics": Date
Applied combinatorics with problem solving
Jackson B., Thoro D., Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1992. Type: Book (9780201129083)
Feb 1 1993
Network design with non simultaneous flows
Lucertini M. (ed), Paletta G., Springer-Verlag New York, Inc., New York, NY, 1984. Type: Book (9780387818160)
Jun 1 1985
Walsh-spectral test for GFSR pseudorandom numbers
Tezuka S. Communications of the ACM 30(9): 731-735, 1987. Type: Article
Jun 1 1988
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy