# 99 questions/Solutions/27

### From HaskellWiki

< 99 questions | Solutions(Difference between revisions)

(This function is purely functional. Use return of do just makes people confusing.) |
m |
||

Line 18: | Line 18: | ||

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

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

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

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

## Revision as of 06:55, 25 November 2010

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