# 99 questions/Solutions/27

### From HaskellWiki

< 99 questions | Solutions

Revision as of 19:40, 18 January 2014 by Henk-Jan van Tuyl (Talk | contribs)

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 and returns them in a list.

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.

combination :: Int -> [a] -> [([a],[a])] combination 0 xs = [([],xs)] combination n [] = [] combination n (x:xs) = ts ++ ds where ts = [ (x:ys,zs) | (ys,zs) <- combination (n-1) xs ] ds = [ (ys,x:zs) | (ys,zs) <- combination n xs ] group :: [Int] -> [a] -> [[[a]]] group [] _ = [[]] group (n:ns) xs = [ g:gs | (g,rs) <- combination n xs , gs <- group ns rs ]

combination

tails

(x:xs)

ts

ds

group

xs

g

rs

gs

g

And a way for those who like it shorter (but less comprehensive):

group :: [Int] -> [a] -> [[[a]]] group [] = const [[]] group (n:ns) = concatMap (uncurry $ (. group ns) . map . (:)) . combination n

And for an intermediate length solution

group :: [Int] -> [a] -> [[[a]]] group [] xs = [[]] group (g:gs) xs = concatMap helper $ combination g xs where helper (as, bs) = map (as:) (group gs bs)