From ... From: Erik Naggum Subject: Re: Q: tail-recursive procedure to generate all permutations of a list Date: 2000/10/04 Message-ID: <3179671668484915@naggum.net>#1/1 X-Deja-AN: 677551538 References: <8qojjq$lr5$1@nnrp1.deja.com> mail-copies-to: never Content-Type: text/plain; charset=us-ascii X-Complaints-To: newsmaster@eunet.no X-Trace: oslo-nntp.eunet.no 970682874 26203 195.0.192.66 (4 Oct 2000 18:07:54 GMT) Organization: Naggum Software; vox: +47 800 35477; gsm: +47 93 256 360; fax: +47 93 270 868; http://naggum.no; http://naggum.net User-Agent: Gnus/5.0803 (Gnus v5.8.3) Emacs/20.7 Mime-Version: 1.0 NNTP-Posting-Date: 4 Oct 2000 18:07:54 GMT Newsgroups: comp.lang.lisp * The Glauber | I'm a novice in Lisp, so bear with me if this is a stupid question. | I've been playing with generating all permutations of a list. | I wrote the following, based on a similar function by Daniel Nesmith: | | (defun permute-list (l) | "Returns a list of all permutations of the input list (list of lists)." | (if (< (length l) 2) | (list l) | ; insert the first element in each position of | ; the permutation of the other elements of the | ; original list | (mapcan | #'(lambda (seq) | (let ((res-list nil)) | (dotimes (i (length l) res-list) | (push | (nconc (subseq seq 0 i) | (cons (first l) (subseq seq i))) | res-list)))) | (permute-list (rest l))))) I tend to favor a slight different approach: (defun permutations (list) (if (cdr list) (loop with rotation = list do (setq rotation (nconc (last rotation) (nbutlast rotation))) nconc (loop for list in (permutations (rest rotation)) collect (cons (first rotation) (copy-list list))) until (eq rotation list)) (list list))) It is about 20 times faster with an 8-element list to permute, but as it turns out, it is significantly more memory-intensive than your approach (4.4 times). (Measured with Allegro CL 6.0.) | Are there any obvious optimizations i missed? That (setq rotation (nconc (last rotation) (nbutlast rotation))) eventually returns the original list and that it can thus be used in a recursive function to avoid duplicating the control structre is not obvious (according to a colleague I showed this to :). That particular expression may also be optimized to traverse the list only once, if you really have to. (For a 10-element list, 98% of the time is spent in garbage collection.) | Is there any way to make this tail-recursive? More interesting than this unnatural obsession with tail-recursion is how deep your recursion is relative to the length of the input. If you can't immediately tell, you need to spend more time with recursion and completely forget tail-recursion until you can get a sufficiently good "gut feeling" for maximal recursion depths. | The next step, i guess, would be to write a macro | with-all-permutations, which would take a list and a block, and run | that block once for each of the permutations of the list. But i | can't see how to do that without first going through the whole | process of generating all the permutations... Pass in a function call, wrap the macro body in a lambda, and off you go. Remember to do this only at the top-level call, and default to some innocuous function like identity. #:Erik -- If this is not what you expected, please alter your expectations.