Consider an algorithm that takes the input a finite set $X$ and an integer partition $\sum_{i=1}^k n_i=|X|$ and gives output all the set partitions $\left(S_1,\ldots, S_k\right)$ of $S$ satisfying $|S_i|=n_i$, for $1\leq i\leq k$. Can someone please describe the steps to execute this and describe the runtime complexity of doing so? The number of these partitions will be the multinomial coefficient $\frac{\left(|X|\right)!}{n_1!\ldots n_k!}$.
1
-
$\begingroup$ We'd prefer that you not delete your question after receiving an answer. Part of our purpose is to build an archive of knowledge that will be useful to others in the future, and answerers may be answering with that mission in mind, so some people might consider it impolite to delete the question once you've received an answer. $\endgroup$– D.W. ♦Commented Apr 14 at 2:32
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
It should help to see that if $(S_1, …, S_k)$ is a set partition for input $(X, n_1, …, n_k)$, then $(S_2, …, S_k)$ is a set partition for input $(X\setminus S_1, n_2, …, n_k)$.
Now you just need to be able to create all subsets $S_1\in \mathcal{P}_{n_1}(X)$ and use the previous idea to create a recursive algorithm.
