;;; Haven't we all felt the need of generating combinations from a collection ;;; and calling a function for every combination? ;;; ;;; It's about as easy as this: ;;; <list> is the initial set ;;; <num> is the number of elements in the resulting combination ;;; <func> is the callback function (defun call-with-combination (list num func &optional acc) (declare (list list acc) (fixnum num) (function func)) (if (zerop num) (apply func acc) (loop for elt in list do (call-with-combination (remove elt list) (1- num) func (cons elt acc)))))
Ingvar ingvar@cathouse.bofh.se writes:
Haven't we all felt the need of generating combinations from a collection and calling a function for every combination?
I wrote one a while ago that may cons less because it requires use of vectors to represent the sequences. The interface to call-with-combinations is similar to yours, with the argument order mixed up.
There's a lower-level function call-with-n-combo-slots that is useful when one has both the source and working "target" vectors in hand. The target vector is used to present the caller-provided function with the current combination, similar to your "acc" argument.
;;; Combinations
(defun call-with-last-combo-slots (function source-vector start end target-vector pos) (loop for i from start below end do (setf (aref target-vector pos) (aref source-vector i)) (funcall function target-vector)))
(defun call-with-n-combo-slots (function source-vector src-start src-end target-vector tgt-start tgt-end) (labels ((rec (function source-vector src-start src-end target-vector tgt-start tgt-end) (let ((slots-remaining (- tgt-end tgt-start))) (if (= 1 slots-remaining) (call-with-last-combo-slots function source-vector src-start src-end target-vector tgt-start) (loop for i-src from src-start to (- src-end slots-remaining) do (setf (aref target-vector tgt-start) (aref source-vector i-src)) (rec function source-vector (1+ i-src) src-end target-vector (1+ tgt-start) tgt-end)))))) ;; TODO: This check is redundant when called from the function ;; below, but we want to protect the core loop above from ;; unchecked calls. We could just factor it out into a ;; non-exported function. (when (> tgt-end tgt-start) (rec function source-vector src-start src-end target-vector tgt-start tgt-end))))
(defun call-with-combinations (function k vector &key (start 0) (end (length vector))) (check-type k (integer 0) "a nonnegative integer") (when (not (zerop k)) ;; TODO: Consider validating start and end. (when (< (- end start) k) (error "Not enough source slots to fill ~A target slots." k)) (call-with-n-combo-slots function vector start end (make-array k :element-type (array-element-type vector)) 0 k)))
#+test (call-with-n-combo-slots #'print (vector 1 2 3 4 5) 0 5 (vector 0 0 0) 0 2)
#+test (call-with-combinations #'print 3 (vector 1 2 3 4 5))
"Steven E. Harris" seharris@raytheon.com writes:
I wrote one a while ago that may cons less because it requires use of vectors to represent the sequences.
Following up to myself, if you're interested, I also have similar code to produce permutations from a source vector, though the permutation algorithm operates destructively in-place on the source sequence.
It's been about six months since I was doing the analysis for this code, but I recall some interesting interdependencies between combinations and permutations. Unfortunately my notes are at home right now.
For example, one can compute /how many/ permutations exist for a full draw from a set (n!), or how many permutations exist for a draw k from a set (n!/(n - k)!), but computing how many combinations exist for any draw k is dependent upon the related permutation count (P/k!).¹
However, to actually come up with the /specific/ permutations and combinations, the dependency is reversed. One can come up with combinations in any draw k independently. One can also come up with permutations for a full draw independently. But to come up with the permutations for some draw k, one must first generate the combinations of draw k, then permute each of those combinations as a full draw. The apparent independence of the full draw permutations is due to there being only one combination to permute for a full draw.
Footnotes: ¹ http://www.themathpage.com/aPreCalc/permutations-combinations.htm
-
Ingvar -
Steven E. Harris