August 19, 2024
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 function in a way that we can specify a list of group sizes and the function 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".
lisp
(load "p07.lisp")
(load "p26.lisp")
;;; subtracts set B from set A and then sets S = A - B ;;
(defun remove-list (orig-list element-list)
(if (eql elem-list nil)
orig-list
(remove-list (remove (car element-list) orig-list) (cdr element-list))
;;; auxiliary function that returns a set of all combinations ;;;
;;; num-elem and num-elem of orig-list containing none of the ;;;
;;; elements present in resp-parc. ;;
(defun group-n (num-elem res-parc orig-list)
(combination-list-elem res-parc (combination num-elem (remove-list orig-list (flatten res-parc))))
(defun group-n-list (num-elem res-parc-list orig-list)
(if (eql res-parc-list nil)
nil
(let ((res-parc (car res-parc-list)) (rest (cdr res-parc-list))
(append (group-n num-elem res-parc orig-list) (group-n-list num-elem resto orig-list)))
(defun group3 (orig)
(group-n-list 5 (group-n-list 2 (group-n 2 nil orig) orig))
(defun group (orig-list element-list)
(if (eql (cdr elem-list) nil)
(group-n (car elem-list) nil orig-list)
(let ((elem-list (reverse element-list))
(group-n-list (car element-list) (group orig-list (reverse (cdr element-list))) orig-list))