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}$? 
 A: 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.  
A: K.C. Locey, Random integer partitions with restricted numbers of parts

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.
