Parallel algorithms for generating subsets and set partitions | SpringerLink
Skip to main content
Springer Nature Link
Log in

Parallel algorithms for generating subsets and set partitions

  • Conference paper
  • First Online:
Algorithms (SIGAL 1990)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 450))

Included in the following conference series:

Abstract

We present adaptive and cost-optimal parallel algorithms for generating 1) all subsets of the set {1,...,n}, 2) all limited size subsets (each subset has at most m elements for a given m), and 3) all partitions of the set. The algorithms are based on a simple model of parallel computation which assumes the existence of k individual processors operating synchronously without need to communicate among themselves. Parallel ranking and unranking procedures for each case are also presented. Applications of the parallel subset generation algorithm to subset-sum, knapsack and base-enumeration problems are subsequently presented.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. S.G. Akl, Adaptive and optimal parallel algorithms for enumerating permutations and combinations. The Computer Journal 30, 5 (1987), 433–436.

    Google Scholar 

  2. S. Baase, Computer Algorithms, Introduction to design and analysis, 2nd ed. Addison-Wesley, Reading, Mass. (1988).

    Google Scholar 

  3. M. Carkeet, P. Eades, Performance of subset generating algorithms. Annals of Discrete Mathematics 26 (1985), 49–58.

    Google Scholar 

  4. B. Chan and S.G. Akl, Generating combinations in parallel. BIT 26, 1 (1986), 2–6.

    MathSciNet  Google Scholar 

  5. K.M. Chandy, J. Misra, Parallel Program Design, A foundation, Addison-Wesley, Reading, Mass. (1988).

    Google Scholar 

  6. G.H. Chen and M.-S. Chern, Parallel generation of permutations and combinations. BIT 26 (1986), 277–283.

    MathSciNet  Google Scholar 

  7. B. Djokić, M. Miyakawa, I. Semba, S. Sekiguchi and I. Stojmenović, A fast iterative algorithm for generating set partitions. The Computer Journal 32, 3 (1989), 281–282.

    Google Scholar 

  8. M.C. Er, Lexicographic enumeration, ranking and unranking of permutations of r out of n objects. International Journal of Computer Mathematics 23 (1987), 1–7.

    Google Scholar 

  9. M.C. Er, Fast algorithm for generating set partitions. The Computer Journal 31, 3 (1988), 283–284.

    Google Scholar 

  10. H. Fredricksen, A survey of full length nonlinear shift register cycle algorithms. SIAM Review 24, 2 (1982), 195–221.

    Google Scholar 

  11. P. Gupta and G.P. Bhattacharjee, Parallel generation of permutations. The Computer Journal 26, 2 (1983), 97–105.

    Google Scholar 

  12. E. Horowitz and S. Sahni, Computing partitions with applications to the knapsack problem. Journal of the ACM 21, 2 (1974), 277–292.

    Google Scholar 

  13. E.D. Karnin, A parallel algorithm for the knapsack problem. IEEE Transactions on Computers C-33, 5 (1984), 404–408.

    Google Scholar 

  14. G.D. Knott, A numbering system for combinations. Communications of the ACM 17, 1 (1974), 45–46.

    Article  Google Scholar 

  15. G.D. Knott, A numbering system for permutations of combinations. Communications of the ACM 19, 6 (1976), 355–356.

    Google Scholar 

  16. G. Li and B.W. Wah, Coping with anomalies in parallel branch-and-bound algorithms. IEEE Transactions on Computers C-35, 6 (1986), 568–573.

    Google Scholar 

  17. M. Miyakawa, I. Stojmenović, D. Lau and I. G. Rosenberg, Classifications and base enumerations in many-valued logics — a survey —, Proc. 17th International Symposium on Multiple-Valued Logic, Boston (May 1987), 152–160.

    Google Scholar 

  18. A. Nijenhuis and H.S. Wilf, Combinatorial Algorithms, Academic Press, New York (1978).

    Google Scholar 

  19. J.G. Peters, L. Rudolph, Parallel approximation schemes for subset sum and knapsack problems. Acta Informatica 24 (1987), 417–432.

    Article  Google Scholar 

  20. Pogosyan G., Miyakawa M. and Nozaki A. On the number of Boolean clique functions, submitted for publication (1988).

    Google Scholar 

  21. Z.G. Qiang, An O(log n) parallel algorithm for the subset sum problem. ACM SIGACT News 18, 2 (Fall 86-Winter 87), 57–63.

    Google Scholar 

  22. C.C. Ribeiro, Parallel computer models and combinatorial algorithms. Annals of Discrete Mathematics 31 (1987), 325–364.

    Google Scholar 

  23. E.M. Reingold, J. Nievergelt and N. Deo, Combinatorial Algorithms, Theory and Practice, Prentice Hall, Englewood Cliff (1977).

    Google Scholar 

  24. I. Semba, A note on enumerating combinations in lexicographical order. Journal of Information Processing 4, 1 (1981), 35–37.

    Google Scholar 

  25. I. Semba, An efficient algorithm for generating all k-subsets (1 ≤ k ≤ m ≤ n) of the set {1, 2, ..., n} in lexicographic order. Journal of Algorithms 5 (1984), 281–283.

    Google Scholar 

  26. I. Semba, An efficient algorithm for generating all partitions of the set {1, ..., n}, Journal of Information Processing 7 (1984), 41–42.

    MathSciNet  Google Scholar 

  27. I. Stojmenović and M. Miyakawa, Applications of subset generating algorithm to base enumeration, knapsack and minimal covering problems. The Computer Journal 31, 1 (1988), 65–70.

    Google Scholar 

  28. M.B. Wells, Elements of Combinatorial Computing, Pergamon Press, Oxford (1971).

    Google Scholar 

  29. B.W. Wah, G. Li and C.F. Yu, Multiprocessing of combinatorial search problems. IEEE Computer (June 1985), 93–108.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Pediatrics Information Systems, University of Miami, P.O. Box 016820, 33101, Miami, Florida, USA

    Borivoje Djokić

  2. Electrotechnical Laboratory, 1-1-4 Umezono, Tsukuba, 305, Ibaraki, Japan

    Masahiro Miyakawa & Satoshi Sekiguchi

  3. Ibaraki University, 2-1-1 Bunkyou, Mito-shi, 310, Ibaraki, Japan

    Ichiro Semba

  4. Dept. of Comp. Sci., University of Ottawa, 34 G. Glinski, K1N 6N5, Ottawa, Canada

    Ivan Stojmenović

Authors
  1. Borivoje Djokić
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Masahiro Miyakawa
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Satoshi Sekiguchi
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Ichiro Semba
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Ivan Stojmenović
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Tetsuo Asano Toshihide Ibaraki Hiroshi Imai Takao Nishizeki

Rights and permissions

Reprints and permissions

Copyright information

© 1990 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Djokić, B., Miyakawa, M., Sekiguchi, S., Semba, I., Stojmenović, I. (1990). Parallel algorithms for generating subsets and set partitions. In: Asano, T., Ibaraki, T., Imai, H., Nishizeki, T. (eds) Algorithms. SIGAL 1990. Lecture Notes in Computer Science, vol 450. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-52921-7_57

Download citation

  • DOI: https://doi.org/10.1007/3-540-52921-7_57

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-52921-7

  • Online ISBN: 978-3-540-47177-6

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation