{- | Description: Group into disjoint subsets Copyright: Copyright (C) 2021 Yoo Chung License: GPL-3.0-or-later Maintainer: dev@chungyc.org Part of Ninety-Nine Haskell "Problems". Some solutions are in "Solutions.P27". -} module Problems.P27 (disjointGroups) where import qualified Solutions.P27 as Solution -- $setup -- >>> import Data.List (sort) {- | In how many ways can a group of 9 people work in 3 disjoint subgroups of 2, 3, and 4 persons? Given a list with the sizes of each group and list of items, write a function to return the list of disjoint groups. Group sizes are larger than zero, and all items in the list to group are distinct. Note that we do not want permutations of the group members. E.g., @[1,2]@ is the same group as @[2,1]@. However, different groups in the list are considered distinct. E.g., @[[1,2],[3,4]]@ is considered a different list of groups from @[[3,4],[1,2]]@. You may find more about this combinatorial problem in a good book on discrete mathematics under the term [/multinomial coefficients/](https://brilliant.org/wiki/multinomial-coefficients/). === Examples >>> let names = ["aldo","beat","carla","david","evi","flip","gary","hugo","ida"] >>> minimum $ map (map sort) $ disjointGroups [2,3,4] names [["aldo","beat"],["carla","david","evi"],["flip","gary","hugo","ida"]] >>> length $ disjointGroups [2,3,4] names 1260 >>> length $ disjointGroups [2,2,5] names 756 -} disjointGroups :: [Int] -> [a] -> [[[a]]] disjointGroups :: forall a. [Int] -> [a] -> [[[a]]] disjointGroups = [Int] -> [a] -> [[[a]]] forall a. [Int] -> [a] -> [[[a]]] Solution.disjointGroups