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".