Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
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:
Taking a partition of $[n-1]$ into $k-1$ ordered subsets, and adding a new subset containing only $n$.
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.
As D.W. mentions, this is just the recurrence for the Stirling numbers.
