August 23, 2024
P27 - Group the elements of a set into disjoint subsets.
a) 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.
Example:
> p27:group3(["A", "B", "C", "D", "E", "F", "G", "H", "I"]).
[[["A","B"],["C","D","E"],["F","G","H","I"]],
[["A","B"],["C","D","F"],["E","G","H","I"]]...b) 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.
Example:
> p27:group([1,2], ["A", "B", "C"]).
[[["A"],[["B","C"]]],
[["B"],[["A","C"]]],
[["C"],[["A","B"]]]]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".
erlang
%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.
-module(p27).
-export([group/2, group3/1]).
group([], []) ->
[];
group([_ | []], Ls) ->
[[Ls]];
group([G | Rest], Ls) ->
F = p26:combinations(G, Ls),
lists:flatmap(fun(Comb) ->
E = group(Rest, Ls -- Comb),
lists:map(fun(B) -> [Comb] ++ B end, E)
end ,F).
group3(Ls) -> group([2,3,4], Ls).