99 Clojure Problems – 27: Group the Elements of a Set into Disjoint Subsets

1. In how many ways can a group of 9 people work in 3 disjoint subgroups of 2, 3 and 4 persons? Write a function that generates all the possibilities.
2. Generalize the above predicate in a way that we can specify a list of group sizes and the predicate will return a list of groups.

Note that we do not want permutations of the group members; i.e. ((Aldo, Beat), ...) is the same solution as ((Beat, Aldo), ...). However, we make a difference between ((Aldo, Beat), (Carla, David), ...) and ((Carla, David), (Aldo, Beat), ...).

You may find more about this combinatorial problem in a good book on discrete mathematics under the term "multinomial coefficients".

Example

(deftest p27-multinomial-coeffients
  (is (=
       '((("Peter" "Paul") ("Mary")) 
         (("Peter" "Mary") ("Paul")) 
         (("Paul" "Mary") ("Peter")))
       (group [2 1] ["Peter" "Paul" "Mary"]))))

Solution

The mulinomial coefficients are a generalisation of the binomial coefficients that we saw in the last problem. $${n \choose k_1, k_2, \ldots, k_m} = \frac{n!}{k_1!\, k_2! \cdots k_m!}$$ I used this to validate some aspects of my solution as you can see in the tests. Showing the correctness of your solution in a traditional unit test gets quite unwieldy when you have, as in this example, 1260 combinations to check.

My solution to part a) of the problem is based on the idea to reuse the enumeration of all k-combinations of n elements from problem 26. We then take all possible combinations of four people out of the group of nine and remove these people from the set of all people by using Clojures set functions. We continue to do that for the 3-combinations and the 2-combinations and add them into a result vector.

The repeated set creation/difference code is neither elegant nor performant but a pragmatic choice given that the combinations function was supposed to work with/return lists. Another area for improvement is the calculation of the last k-combinations. It is redundant as its result is just the remainder of the original input sequence.

The solution to part b) is a bit more involved but very closely related in terms of its structure. It's a recursive solution that starts with calculating the combinations for the first group and mapping the result to a recursive self-call. In each recursive call we remove the elements/persons already "used" from the input set. We also remove the k for which we just calculated the combinations from the list of group sizes. The whole operation is wrapped in a mapcat to flatten the result into just one level as you can see in the example.

Read more about this series.