Generate integer and set partitions

Object type
Size $n$ of the integer/set	(max. 15)
Number $m$ of parts/blocks	(between 1 and $n$)
Output format

Output  numbering graphics

An integer partition of a number $n$ is a way of writing $n$ as a sum of positive smaller numbers, called parts, where the parts appear in non-increasing order. For instance, the seven integer partitions of 5 are $5=4+1=3+2=3+1+1=2+2+1=2+1+1+1=1+1+1+1+1$. An integer partition can be visualized by its Ferrers diagram, which consists of a sequence of rows of boxes, and the number of boxes in each row from top to bottom is given by the parts in the partition. For instance, the partitions of 5 from before yield the diagrams shown in the following figure.

There is also a notion of ordered partitions of an integer $n$, called integer compositions. For example, in the seven aforementioned integer partitions of 5, the parts can be ordered in 1,2,2,3,3,4,1 different ways, respectively, yielding 1+2+2+3+3+4+1=16 integer compositions of 5 overall. Since integer compositions of $n$ are in bijection to binary strings of length $n-1$, they can be generated by the binary reflected Gray code.

A set partition of a ground set $[n]:=\{1,\ldots,n\}$ is a partition of this set into nonempty subsets called blocks. A set partition is ordered or unordered, if the ordering of the blocks matters or not, respectively. The ordering of elements in each block is irrelevant, and we use lexicographic ordering without loss of generality. For instance, all five unordered set partitions of the ground set $[3]$ are $123,12|3,1|2|3,1|23,13|2$, where the boundaries between blocks are indicated by vertical bars, and set brackets are omitted for simplicity. The blocks in those five partitions can be (re)ordered in 1,2,6,2,2 different ways, respectively, yielding in total 1+2+6+2+2=13 different ordered set partitions of $[3]$. Note that ordered set partitions of $[n]$ with $n$ blocks are permutations.

The first two algorithms running on this website are part of Jörg Arndt's FXT library. Algorithms for generating integer partitions are described in Algorithms P and H in Knuth's book [Section 7.2.1.4, Knu11]. An algorithm for generating unordered set partitions is described as Algorithm H in Knuth's book [Section 7.2.1.5, Knu11].

The algorithm for listing ordered set partitions is described in the paper [BBM+25], and it has the Gray code property, i.e., any two consecutive partitions either differ in adding a bar inside a block, splitting it into two, or by removing a bar between two blocks, taking their union. The resulting listing corresponds to a Hamilton path in the face lattice of the permutahedron that starts and ends at a face of dimension 0 (a permutation). Via the trivial face $\emptyset$ this Hamilton path can be completed to a Hamilton cycle in the face lattice.

The number of integer partitions is given by the partition numbers (OEIS A000041). Furthermore, unordered set partitions are counted by the Bell numbers (OEIS A000110), and ordered set partitions by the Fubini numbers (OEIS A000670).

[Zipped C++ source code (GNU GPL)]
[Link to Jörg Arndt's FXT library (GNU GPL)]

• [BBM+25] N. Behrooznia, S. Brenner, A. Merino, T. Mütze, C. Rieck, and F. Verciani. Listing faces of polytopes. arXiv:2412.02584, Aug 2025.
• [Knu11] D. E. Knuth. The Art of Computer Programming. Vol. 4A. Combinatorial Algorithms. Part 1. Addison-Wesley, Upper Saddle River, NJ, 2011.