# 99 questions/Solutions/27

### From HaskellWiki

< 99 questions | Solutions(Difference between revisions)

(3 intermediate revisions by 2 users not shown) | |||

Line 15: | Line 15: | ||

group :: [Int] -> [a] -> [[[a]]] | group :: [Int] -> [a] -> [[[a]]] | ||

− | group [] _ = | + | group [] _ = [[]] |

− | group (n:ns) xs = | + | group (n:ns) xs = |

− | (g,rs) <- combination n xs | + | [ g:gs | (g,rs) <- combination n xs |

− | + | , gs <- group ns rs ] | |

− | + | ||

</haskell> | </haskell> | ||

Line 32: | Line 31: | ||

group (n:ns) = concatMap (uncurry $ (. group ns) . map . (:)) . combination n | group (n:ns) = concatMap (uncurry $ (. group ns) . map . (:)) . combination n | ||

</haskell> | </haskell> | ||

+ | |||

+ | And for an intermediate length solution | ||

+ | <haskell> | ||

+ | group :: [Int] -> [a] -> [[[a]]] | ||

+ | group [] xs = [[]] | ||

+ | group (g:gs) xs = concatMap helper $ combination g xs | ||

+ | where helper (as, bs) = map (as:) (group gs bs) | ||

+ | </haskell> | ||

+ | |||

+ | |||

+ | [[Category:Programming exercise spoilers]] |

## Latest revision as of 19:40, 18 January 2014

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)