The Algorithm Design Manual
About the Book
Programming Challenges

The Stony Brook Algorithm Repository

Steven Skiena
Stony Brook University
Dept. of Computer Science

1.3.6 Generating Partitions

Problem Input | Problem Output

INPUT                    OUTPUT


Input Description: An integer n.

Problem: Generate (1) all, or (2) a random, or (3) the next integer or set partitions of length n.

Excerpt from The Algorithm Design Manual: There are two different types of combinatorial objects denoted by the term ``partition'', namely integer partitions and set partitions. Although they are quite different beasts, it is a good idea to make both a part of your vocabulary:


Implementations

  • C.A.G.E.S. (C) (rating 10)
  • Frank Ruskey's Combinatorial Generation Resources (C,Pascal) (rating 9)
  • Nijenhuis and Wilf: Combinatorial Algorithms (FORTRAN) (rating 8)
  • FFT - Fast Fourier Transform (C,FORTRAN) (rating 8)
  • Combinatorica (Mathematica) (rating 7)
  • ParMetis 2.0 - A package for graph partitioning (C) (rating 7)

  • Recommended Books

    The Art of Computer Programming, Volume 4 Fascicle 4: Generating All Trees; History of Combinationatorial Generation by D. E. Knuth The Art of Computer Programming, Volume 4 Fascicle 3: Generating All Combinations and Partitions by D. E. Knuth The Theory of Partitions by G. Andrews

    Related Problems


      
    Generating Permutations
      
    Generating Subsets
      
    Random Number Generation
      
    Set Data Structures



    This page last modified on 2008-07-10 .
    www.algorist.com