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

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

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
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.

• How do I generate $C$? Also what does $S-T$ mean? Are you removing all elements of $T$ from $S$? BTW the elements aren't necessarily letters, so you can't check its lexicographic order. – Martin Nov 7 '17 at 7:40
• For generating $C$ please look here. I gave it at the end of my post. $S-T$ means difference of sets $S$ and $T$, i.e., you subtract elements of $T$ from $S$. Any finite set can be sorted in lexicographic order, in particular integers. But that is optional for this algorithm. – fade2black Nov 7 '17 at 7:52
• I tried translating the java implementation from your link to javascript, but it only prints the first 4 arrays. Code: pastebin.com/3xPCEpmP – Martin Nov 7 '17 at 8:58
• I can't say anything , neither can I debug your code. If your code does not work then you probably made a mistake or translated it incorrectly. Please double check. This is another link. – fade2black Nov 7 '17 at 9:05
• I fixed it by translating the c++ code from your link instead. But I can't get your generate function from your first solution to work properly. Could you check it to see if I have implemented your algorithm correctly? pastebin.com/06ViALt2 – Martin Nov 7 '17 at 16:01