Does anyone have anycode to go through all the possible combinations
of objects in a list?
I had a working version in c, and i am redoing the program in lisp but
i think the algorithm was pretty weak anyways and there is a better
way to do it..
i want to be able to loop through all possible combinations of size m
with n objects...
here's the code i have so far.. and this is not a homework problem,
but its for some algorithm research...
thanks for any help... if any one just has a specific algorithm to do
it other than the way i was trying that would be helpful too..
;void nextcomb(int *a, int max, int limit)
;{
; int x;
; int i;
; int reset;
; for (x=limit;x > -1; x--)
; {
; a[x]++;
; if (a[x]<=max)
; break;
; reset = 1;
; }
; if (reset)
; {
; for (i = x+1; i <= limit; i++)
; {
; a[i]=a[i-1]+1;
; }
; reset=0;
; }
; if (a[limit] > max && a[0]<=max-limit)
; nextcomb(a, max, limit);
;}
;resetcomb(int *a, int limit)
;{
; int i;
; for (i=0;i<=limit;i++)
; {
; a[i]=i;
; }
;}
(defun resetcomb (limit)
(let ((list nil))
(dotimes (i limit)
(push i list))
(reverse list)))
(defun nextcomb (thelist max limit)
(let ((reset nil) (x 0))
(setq x
(catch 'break
(do ((x (1- max) (1- x)))
((<= x 1) x)
(format t "x = ~a~%" x)
(format t "thelist[x] = ~a~%" (nth x thelist))
(incf (nth x thelist))
(when (>= (nth x thelist) max)
(throw 'break x))
(setq reset t))
(throw 'break limit)))
(when reset
(do ((i (1+ x) (1+ i)))
((> i limit) nil)
(setq reset nil)))
(format t "here~%")
(if (and (> (nth (1- max) thelist) max)
(<= (car thelist) (- max limit)))
(nextcomb thelist max limit)
thelist)))
--
(setq sig '((Christopher Bowron)
(········@cps.msu.edu)
(www.cps.msu.edu/~bowronch)
("we came, we saw, we got bored and left")))
(defun combinations (k li)
"Return all combinations of k elements out of the list li."
(let* ((l (length li))
(sli (subseq li 0 (1+ (- l k))))
(rli (rest li)))
(if (= 1 k) (mapcar #'list li)
(loop for el in sli
append (mapcar #'(lambda (co)
(cons el co))
(combinations (1- k) rli))
do (setf rli (rest rli))))))
--
Joachim De Beule,
tel: +32 9 2646541
email: ·······@inwpent3.rug.ac.be
A better thing to do, IMHO, would be to allow for a third argument to act
as a callback. In such cases especially, I find that even for a small input
argument the potential for getting back a *huge* return value is there, and
the extra consing often turns out to be unnecessary, a throwaway. The
calling program then has the option to collect those values in the handler,
if so desired.
My version:
(defun combinations (k list handler)
(let ((length (length list)))
(if (>= k length)
(funcall handler list)
(%combinations k nil length list handler))))
(defun %combinations (required collected available items handler)
(cond ((= required available) (funcall handler (append collected items)))
((= required 0) (funcall handler collected))
(t (%combinations (1- required) (cons (car items) collected)
(1- available) (cdr items)
handler)
(%combinations required collected
(1- available) (cdr items)
handler))))
Appears to work fine. You will have to modify this if you want to preserve
order.
Sunil
joachim de beule <·······@inwpent3.rug.ac.be> writes:
> (defun combinations (k li)
> "Return all combinations of k elements out of the list li."
> (let* ((l (length li))
> (sli (subseq li 0 (1+ (- l k))))
> (rli (rest li)))
> (if (= 1 k) (mapcar #'list li)
> (loop for el in sli
> append (mapcar #'(lambda (co)
> (cons el co))
> (combinations (1- k) rli))
> do (setf rli (rest rli))))))
> --
> Joachim De Beule,
> tel: +32 9 2646541
> email: ·······@inwpent3.rug.ac.be