# Algorithm to split $n$ distinct items into $k$ nonempty unlabelled subsets

The number of ways to split $n$ items into $k$ nonempty unlabelled subsets ($k<n$) is a Stirling number of the second kind.(https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind)

Is there an algorithm to generate all the possible combinations?

• You can derive such an algorithm directly from the recurrence for these numbers.
– D.W.
Mar 5 '17 at 13:58

Concretely, let us count the number of ways to partition $[n]$ into $k$ non-empty ordered subsets, which are themselves ordered by increasing order of the first element. For example, a valid partition of 10 into 5 sets is $$\{1,4,5\},\{2,3,6\},\{7\},\{8,10\},\{9\}.$$ Note that $1<2<7<8<9$.
The base cases $k=0,k=1,k=n$ are easy, so suppose $2 \leq k < n$. A partition of $[n]$ into $k$ ordered subsets can be obtained in two ways:
1. Taking a partition of $[n-1]$ into $k-1$ ordered subsets, and adding a new subset containing only $n$.
2. Taking a partition of $[n-1]$ into $k$ ordered subsets, and adding $n$ to the 1st subset, the 2nd subset, ..., the $k$th subset.
By recursively generating all partitions of $[n-1]$ into $k-1$ or $k$ ordered subsets, you can thus generate all partitions of $[n]$ into $k$ ordered subsets.