Group the elements of a set into disjoint subsets

	;; P27 (**) 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) )
	;; ... )
	;; 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) )
	;; ... )
	;; Note that we do not want permutations of the group members; i.e. ((ALDO BEAT) ...) is the same solution as ((BEAT ALDO) ...). However, we make a difference between ((ALDO BEAT) (CARLA DAVID) ...) and ((CARLA DAVID) (ALDO BEAT) ...).
	;; You may find more about this combinatorial problem in a good book on discrete mathematics under the term "multinomial coefficients".
	(require "p07.ss")
	(require "p26.ss")
	(define (remove-list old new)
	(if (null? new)
	old
	(remove-list (remove (car new) old) (cdr new))))
	(define (group-n num result old)
	(combination-aux
	result
	(combination num
	(remove-list old
	(flatten result)))))
	(define (group-n-aux num result lst)
	(let loop ((result result) (acc '()))
	(if (null? result)
	acc
	(let ((head (car result))
	(tail (cdr result)))
	(loop tail
	`(,@acc ,@(group-n num head lst)))))))
	(define (group3 lst)
	(group-n-aux 4
	(group-n-aux 3
	(group-n 2 '() lst)
	lst)
	lst))
	(define (group old new)
	(if (null? (cdr new))
	(group-n (car new) '() old)
	(let ((lst (reverse new)))
	(group-n-aux (car lst)
	(group old (reverse (cdr lst)))
	old))))

view raw p27.ss hosted with ❤ by GitHub