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

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\{{n1 \atop k1}\right \}+k \left\{{n1 \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, n1\}$. This recursion can also be used to generate a set partition recursively: With probability $\left\{{n1 \atop k1}\right \}/\left\{{n \atop k}\right \}$ put $n$ in its own set, and make the rest a partition of $n1$ elements into $k1$ sets chosen uniformly at random. Otherwise generate a uniform random partition of $n1$ 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. 


K.C. Locey, Random integer partitions with restricted numbers of parts
This algorithm was developed by Ken Locey in response to a 2010 question on StackOverflow. 

