# Enumerate partitions of a set with blocks of equal size

Given a set $\{1,\ldots,ck\}$, is there a known algorithm to efficiently list all partitions in with $c$ blocks of cardinality $k$?

In The art of computer programming (Fascicle 3B) by Knuth, there's a mention of an algorithm by Ruskey that can list all partitions with $c$ blocks. I could just use this algorithm and discard all partitions that violate the constraint on the equal size of blocks, but I would visit many useless partitions.

Is there a better way?

I don't know if there is a known algorithm, but there is an obvious algorithm: a partition is given by a subset $S$ of $\{1,...,ck\}$ containing the number $1$ and having cardinality $k$, plus a partition of the remaining $(c-1)k$ elements in subsets of cardinality $k$.

This gives a recursive algorithm provided one lists efficiently all subsets of $\{2, ..., ck\}$ having cardinality $k-1$.

Suppose that we have a function $subsets(A, n)$ that lists all the subsets having cardinality n in a set A. We define a function $partitions(A, k)$ that lists all the partitions of $A$ in subsets having cardinality $k$, provided $|A|$ is a multiple of $k$:

function partitions(A, k):
if A is empty:
yield the empty partition
else:
let a be an arbitrary element of A
for each S in subsets(A \ {a}, k-1):
X = S union {a}
for each P in partitions(A \ X, k):
yield P union {X}
end

• I don't know if I got your idea... let me try to rephrase it: I start by considering $1$ and forming a $k$-block only with elements $>1$ (all of the remaining, in this case). I proceed by considering $2$, etc... Each time I go down a level, I am allowed to form $k$-blocks with the considered element or greater elements, if possible (i.e., if the considered element isn't already in a $k$-block with an upper element. By doing so we shouldn't generate the same partition multiple times. When I have exhausted all the possible $k$-block in one level, I backtrack up and go on with the next $k$-block. – Filippo Bistaffa Aug 1 '17 at 10:11
• See my edit with pseudocode. – Gribouillis Aug 1 '17 at 11:06
• I implemented this and it seems to work. – Filippo Bistaffa Aug 1 '17 at 14:07
• Do you have a link to your implementation? – Gribouillis Aug 1 '17 at 14:09
• How do you generate the subsets? In a similar recursive way, I assume. – miracle173 Aug 1 '17 at 14:16

Section 5.10 of Ruskey's book Combinatorial Generation gives a combinatorial Grey code for linear extensions of posets and describes a bijection between set partitions of a chosen shape and linear extensions of a corresponding poset.

### Partitions of Given Type

Let $P(n_0, n_1, \ldots, n_t)$ be the set of partitions of the set $\{1, 2, \ldots, n\}$ into blocks of sizes $n_0, n_1, \ldots, n_t$, where $n = n_0 + n_1 + \cdots + n_t$. For example, the partition $\{\{2, 8\}, \{3, 5\}, \{6, 12\}, \{1, 10, 11\}, \{4, 7, 9\}\}$ is in $P(2, 2, 2, 3, 3)$. We have listed the elements in order and the blocks of equal size by the magnitude of their smallest element. The problem of generating the elements of $P$ can be reduced to that of generating the linear extensions of a certain forest poset. The cover relations of the poset consist of chains of sizes $n_i$ together with chains of the maximal elements of the previous chains which have equal values of $n_i$. The linear extension corresponding to our example is $7, 1, 3, 10, 4, 5, 11, 2, 12, 8, 9, 6$. The inverse of this permutation is $2, 8, 3, 5, 6, 12, 1, 10, 11, 4, 7, 9$, which is just our original partition but without the curly braces.

To be a little more precise, assume that the $n_i$ are listed such that $n_0 \le n_1 \le \cdots \le n_t$, and let $s_i = \sum_{j=1}^{i-1} n_i$. The cover relations of the poset are indicated by the $t + 1$ chains $C_i = s_i + 1, s_i + 2, \ldots, s_i + n_i$ and $D_i = s_i + 1, s_{i+1} + 1, \ldots, s_j + 1$, where $n_{i−1} < n_i = n_{i+1} = \ldots = n_j < n_{j+1}$.

The algorithm per se is described in Pruesse and Ruskey, Generating linear extensions fast, SIAM Journal on Computing 23.2 (1994): 373-386.