Generate integer and set partitions

The integer partitions of a number describe all ways to write this number as a sum of positive smaller numbers, called parts, where the order of the parts is irrelevant. Parts are usually listed in decreasing 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$. A number partition can be visualized by a 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.

A set partition of a ground set is a partition of this set into nonempty subsets, where the ordering of the subsets is irrelevant. The ordering of elements in each subset is also irrelevant, and we use lexicographic ordering without loss of generality. For instance, all five set partitions of the ground set $\{1,2,3\}$ are $123,12|3,1|2|3,1|23,13|2$, where the boundaries between subsets are indicated by vertical bars, and subset brackets are omitted for simplicity.

The 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 set partitions is decribed as Algorithm H in Knuth's book [Section 7.2.1.5, Knu11].

The number of integer partitions is given by the partition numbers (OEIS A000041), and the number of set partitions is given by the Bell numbers (OEIS A000110).

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

• [Knu11] D. E. Knuth. The Art of Computer Programming. Vol. 4A. Combinatorial Algorithms. Part 1. Addison-Wesley, Upper Saddle River, NJ, 2011.