Path: utzoo!attcan!uunet!husc6!think!ames!joyce!aai3!miner
From: miner@aai3.uucp (Stephen E. Miner)
Newsgroups: comp.lang.lisp
Subject: Re: permutations
Message-ID: <14337@joyce.istc.sri.com>
Date: 19 Oct 88 16:12:53 GMT
References: <1131@amelia.nas.nasa.gov>
Sender: nobody@joyce.istc.sri.com
Reply-To: miner@sri.com (Stephen E. Miner)
Organization: SRI International, Menlo Park CA
Lines: 52

In article <1131@amelia.nas.nasa.gov> raible@orville.nas.nasa.gov (Eric L. Raible) writes:
>
>(defun permutations (elements)
>  (if (null elements)
>      (list nil)
>      (mapcan
>       #'(lambda (element)
>	   (mapcar
>	    #'(lambda (permutation)
>		(cons element permutation))
>	    (permutations (remove element elements))))
>       elements)))
>
>Comments?  Alternatives?

Here's an alternative...


(defun propagate (element perm)
  "Returns a list of 'propagations' of the ELEMENT through the list PERM."
  (propagate-aux element nil perm))

(defun propagate-aux (element before after)
  "Returns a list of lists each with the prefix BEFORE followed by one of the
possible insertions of ELEMENT into the list AFTER." 
  (if (endp after) 
      (list (append before (list element)))
      (cons (append before (cons element after))
            (propagate-aux element 
		           (append before (list (car after))) 
		           (cdr after)))))

(defun permu-extend (element permu-list)
  "Returns an extended list of permutations by propagating the new
ELEMENT through each of the base permutations in PERMU-LIST."
  (if (endp permu-list)
      nil
      (append (propagate element (car permu-list))
	      (permu-extend element (cdr permu-list)))))

(defun permu (elements)
  "Returns a list of the permutations of the list ELEMENTS."
  (if (endp elements) 
      (list nil)
      (permu-extend (car elements) (permu (cdr elements)))))



Stephen E. Miner
miner@sri.com

	       *** My other computer is a Macintosh ***