From: Christopher William Bowron
Subject: combinations
Date: 
Message-ID: <lxbvhfoetf7.fsf@arctic.cps.msu.edu>
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")))

From: joachim de beule
Subject: Re: combinations
Date: 
Message-ID: <rchfr8jyve.fsf@inwpent3.rug.ac.be>
(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
From: Sunil Mishra
Subject: Re: combinations
Date: 
Message-ID: <efypv5wglv3.fsf@cleon.cc.gatech.edu>
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