2
$\begingroup$

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

|cite|improve this question
$\endgroup$
1
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Martin Nov 7 '17 at 7:40
  • $\begingroup$ 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. $\endgroup$ – fade2black Nov 7 '17 at 7:52
  • $\begingroup$ I tried translating the java implementation from your link to javascript, but it only prints the first 4 arrays. Code: pastebin.com/3xPCEpmP $\endgroup$ – Martin Nov 7 '17 at 8:58
  • $\begingroup$ 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. $\endgroup$ – fade2black Nov 7 '17 at 9:05
  • $\begingroup$ 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 $\endgroup$ – Martin Nov 7 '17 at 16:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.