August 19, 2024
P26 - Generate the combinations of K distinct objects chosen from the N elements of a list
In how many ways can a committee of 3 be chosen from a group of 12 people? We all know that there are C(12,3) = 220 possibilities (C(N,K) denotes the well-known binomial coefficients). For pure mathematicians, this result may be great. But we want to really generate all the possibilities in a list.
Example:* (combination 3 '(a b c d e f))((A B C) (A B D) (A B E) ... )
lisp
;;; Function that returns all possible choices of K elements from a
;;; given list L. Solution courtesy of Martin Buchmann, with cosmetic
;;; editions by JM.
(defun combination (k l)
(cond
((< k 0) nil)
((= k 0) (list nil))
((> k (length l)) nil)
(t (append (mapcar #'(lambda (x) (cons (first l) x))
(combination (1- k) (rest l)))
(combination k (rest l))
)
)
)
)
;;; Alternative solution sent to me by Wojciech Gac on 2014-01-17
;;; Just indentation editing by JM.
(defun combination (n lst)
(cond
((zerop n) nil)
((= n 1) (mapcar #'list lst))
(t (mapcan #'(lambda (x)
(mapcar #'(lambda (y) (append (list x) y))
(combination (1- n) (setf lst (delete x lst)))))
lst))
)
)
Be first to comment