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:


  • 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 .