Algorithm for computing partitions of a set of n elements into subsets of size m

Question

I need an algorithm that can compute all the different partitions of a set of n elements into subsets of size m.

For example for $n=4$ for the set $\{a,b,c,d\}$ and $m=2$ the output should be

$\{\{\{a,b\},\{c,d\}\},\{\{a,c\},\{b,d\}\},\{\{b,c\},\{a,d\}\}\}$

Answer 1

Two possible possible solutions.

Given a set $S$ of size $n$ and a positive integer $m < n$. First generate all $m$-size subsets of $S$, for example, in lexicographic order and store them. Let $C$ be the set of all $m$-size subsets of $S$. The size of $C$ is $\binom{n}{m}$. The following algorithm generates all partitions

Generate(S, Partition)
  if S is empty
    print Partition
    return

  for each T in C such as T is a subset of S
    add T to Partition
    Generate(S-T, Partition)
    remove T from Partition
end

This algorithm repeats partitions but you can check if a Partition repeats. If it does then do not print it. One possible solution is checking its lexicographic order.

The second approach, which I think is simpler, is to systematically generate all $(n/m)$-size subsets of $C$. If for some $(n/m)$-size subset $T$ all sets in $T$ are mutually exclusive, then $T$ is a partition and so print it.

Example: $S=\{a,b,c,d\}$ and so $C = \{\{a,b\},\{a,c\}, \{a,d\}, \{b,c\}, \{b,d\}, \{c,d\}\}$. Then using the second approach we systematically generate all $4/2=2$-size subsets of $C$. Thus while generating if we have $\{\{a,b\},\{a,d\}\}$ then we just skip it since it's not a partition. But if we have $\{\{a,b\},\{c,d\}\}$ then we print it since it is a partition. Furthermore, there is no chance of generating duplicate of a subset of $C$ since we generate all (distinct!) combinations of $4/2=2$ elements from $\binom{4}{2}=6$.

For generating combinations of $k$ elements from $n$ you could look, for example, here.