# Difference between revisions of "99 questions/Solutions/27"

(New solution) |
|||

Line 39: | Line 39: | ||

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

</haskell> |
</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 ]
```

First of all we acknowledge that we need something like `combination`

from the above problem. Actually we need more than the elements we selected, we also need the elements we did not select. Therefore we cannot use the `tails`

function because it throws too much information away. But in general this function works like the one above. In each step of the recursion we have to decide whether we want to take the first element of the list `(x:xs)`

in the combination (we collect the possibilities for this choice in `ts`

) or if we don't want it in the combination (`ds`

collects the possibilities for this case).

Now we need a function `group`

that does the needed work. First we denote that if we don't want any group there is only one solution: a list of no groups. But if we want at least one group with n members we have to select n elements of `xs`

into a group `g`

and the remaining elements into `rs`

. Afterwards we group those remaining elements, get a list of groups `gs`

and prepend `g`

as the first group.

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)
```