# How to efficiently sample uniformly from the set of p-partitions of an n-set?

Let $n,p \in \mathbb{N}_+$ with $p \leq n.$ Let $\mathcal{P}$ denote the set of partitions of $\{1, \ldots, n\}$ into $p$ nonempty sets. How can I efficiently sample uniformly from $\mathcal{P}$?

• I would imagine that a Markov chain with rapid mixing might be useful here, though it would give only approximately uniform distribution. – DmitryZ Sep 12 '13 at 21:24

The sets you're interested in are counted by Stirling Numbers of the Second Kind, which satisfy the recursion $$\left\{{n \atop k}\right \}=\left\{{n-1 \atop k-1}\right \}+k \left\{{n-1 \atop k}\right \}$$ Here the first term represents those partitions where $n$ is its own set, and the remaining term represents inserting $n$ into a partition of $\{1, \dots, n-1\}$. This recursion can also be used to generate a set partition recursively:

With probability $\left\{{n-1 \atop k-1}\right \}/\left\{{n \atop k}\right \}$ put $n$ in its own set, and make the rest a partition of $n-1$ elements into $k-1$ sets chosen uniformly at random. Otherwise generate a uniform random partition of $n-1$ elements into $k$ sets, and insert $n$ into a set uniformly chosen from those sets.

The algorithm would run in time on the order of $nk$, with the main overhead being computing (or looking up) all of the Stirling Numbers up to $\left\{{n \atop k}\right \}$ at the start of the algorithm.

• Hmmm. Efficiency issues aside, this algorithm isn't practical for large n and k unless you're using a CAS that can compute the requisite Stirling numbers and then compute the quotient to reasonable accuracy. – AatG Sep 25 '13 at 20:32

An algorithm is presented to generate uniform random samples of integer partitions for a total $Q$ with $N$ parts from the set of all $P(Q, N)$ partitions.

This algorithm was developed by Ken Locey in response to a 2010 question on StackOverflow.

• Thanks, but I want to sample set partitions, not integer partitions. – AatG Sep 13 '13 at 17:57
• If $N=a_1+\dots + a_k$ is a random integer partition, and $x_1,x_2,\dots,x_N$ is a random permutation, then $\{ \{ x_1,\dots,x_{a_1}\}, \{x_{a_1+1},\dots,x_{a_1+a_2} \}, \dots \}$ is a random set partition. It isn't clear to me that it won't be uniformly random. – Kevin O'Bryant Sep 13 '13 at 21:41
• @KevinO'Bryant it can't be uniformly random, because otherwise we would have $P(n)|B_n$ ($P(n)$ being the number of partitions and $B_n$ the Bell numbers, i.e. the number of set partitions), and it's easy to see this doesn't hold - in fact, it already breaks down for $n=3$ when there are $3$ partitions ($3$, $2+1$, $1+1+1$) and $5$ set partitions ($123$, $1|23$, $2|13$, $3|12$, $1|2|3$). – Steven Stadnicki Sep 14 '13 at 0:31