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