Stony Brook Algorithm Repository

Generating Partitions


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:


CAGES (rating 9)
Frank Ruskey's Combinatorial Generation Resources (rating 8)
Nijenhuis and Wilf (rating 8)
FFT (rating 8)
perfect-layout (rating 7)
linear-partition (rating 7)
ParMetis (rating 7)
Combinatorica (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

Go To Main Page