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

  • $\begingroup$ I would imagine that a Markov chain with rapid mixing might be useful here, though it would give only approximately uniform distribution. $\endgroup$ – 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.

  • $\begingroup$ 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. $\endgroup$ – AatG Sep 25 '13 at 20:32

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.

  • $\begingroup$ Thanks, but I want to sample set partitions, not integer partitions. $\endgroup$ – AatG Sep 13 '13 at 17:57
  • $\begingroup$ 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. $\endgroup$ – Kevin O'Bryant Sep 13 '13 at 21:41
  • 2
    $\begingroup$ @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$). $\endgroup$ – Steven Stadnicki Sep 14 '13 at 0:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.