Sample, randomly & uniformly the partitioning of $n$ objects into $K$ groups

Question

I wish to sample randomly and uniformly from the set of partitions of $n$ objects into $K$ groups where the number to be assigned to each group, $n_k$ ($k = 1, 2, \dots, K$) is known.

I know that the number of partitions is

$$ \frac{n!}{\prod_{k=1}^K n_k!} $$

so that for say $n = 9$ and $n_1 = n_2 = n_3 = 3$, there are

$$ \frac{9!}{3!3!3!} = 1680$$

such partitions. Note I don't wish to restrict myself to equal group sizes.

How can I sample a number, say $P$, of these partitions, such that the resulting sample is drawn randomly and uniformly from the set of all such partitions?

One approach that occurred to me would be to:

1. select a group from the $K$ groups, at random
2. select at random from the $n$ observations $n_1$ of them
3. select at random a group from the remaining $K-1$ groups
4. select at random from the $n - n_1$ remaining observations
5. repeat 3 and 4 until you have filled $K - 1$ groups, assign the remaining observations to the last group.

Does that seem reasonable or am I overlooking something important?

Answer 1

It took me a second to deduce from your example that the combinatorial objects you're interested in are ordered set partitions, i.e., set compositions. The linked webpage is for the ordered set partition functions of the python/cython based SAGE mathematical software.

For example, in the Sage notebook (sagenb.org):
OS = OrderedSetPartitions(9, [3,3,3]) OS.cardinality() 1680
OS.random_element() [{1, 2, 3}, {8, 4, 6}, {9, 5, 7}]

The sage source code is readily available, though you might have to hunt for your particular function.