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}$? 



How to efficiently sample uniformly from the set of p-partitions of an n-set?
The sets you're interested in are counted by [Stirling Numbers of the Second Kind](http://en.wikipedia.org/wiki/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. 


