# S-99-27

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.

Example:

``` (group3 '(aldo beat carla david evi flip gary hugo ida))
;; => ( ( (ALDO BEAT) (CARLA DAVID EVI) (FLIP GARY HUGO IDA) )
;;      ... )
```

Solution:

``` (define (combination k xs)
(cond [(null? xs) '()]
[(= k 1) (map list xs)]
[else (append (map (lambda (x) (cons (car xs) x))
(combination1 (- k 1) (cdr xs)))
(combination1 k (cdr xs)))]))

(define (group3 lst)
(define (loop1 xss full)
(if (null? xss)
'()
(let* ((xs (car xss)) (rest (filter (lambda (e) (not (member e xs))) full)))
(append (map (lambda (ys) (cons xs ys))
(loop2 (combination 3 rest) rest))
(loop1 (cdr xss) full)))))
(define (loop2 yss full)
(if (null? yss)
'()
(let* ((ys (car yss)) (rest (filter (lambda (e) (not (member e ys))) full)))
(append (map (lambda (zs) (list ys zs))
(combination 4 rest))
(loop2 (cdr yss) full)))))
(loop1 (combination 2 lst) lst))
```

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.

Example:

``` (group '(aldo beat carla david evi flip gary hugo ida) '(2 2 5))
;; => ( ( (ALDO BEAT) (CARLA DAVID) (EVI FLIP GARY HUGO IDA) )
;;       ... )
```

Solution:

``` (define (group gs lst)
(define (loop gs xss lst)
(cond [(null? gs) xss]
[(null? xss) '()]
[else
(let* ((xs (car xss)) (rest (filter (lambda (e) (not (member e xs))) lst)))
(append (map (lambda (ys) (list xs ys))
(loop (cdr gs) (combination (car gs) rest) rest))
(loop gs (cdr xss) lst)))]))
(loop (cdr gs) (combination (car gs) lst) lst))
```

You may find more about this combinatorial problem in a good book on discrete mathematics under the term "multinomial coefficients".