From ...
From: Erik Naggum
Subject: Re: Q: tailrecursive procedure to generate all permutations of a list
Date: 2000/10/04
MessageID: <3179671668484915@naggum.net>#1/1
XDejaAN: 677551538
References: <8qojjq$lr5$1@nnrp1.deja.com>
mailcopiesto: never
ContentType: text/plain; charset=usascii
XComplaintsTo: newsmaster@eunet.no
XTrace: oslonntp.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
UserAgent: Gnus/5.0803 (Gnus v5.8.3) Emacs/20.7
MimeVersion: 1.0
NNTPPostingDate: 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 permutelist (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 ((reslist nil))
 (dotimes (i (length l) reslist)
 (push
 (nconc (subseq seq 0 i)
 (cons (first l) (subseq seq i)))
 reslist))))
 (permutelist (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) (copylist list)))
until (eq rotation list))
(list list)))
It is about 20 times faster with an 8element list to permute, but
as it turns out, it is significantly more memoryintensive 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 10element list, 98% of
the time is spent in garbage collection.)
 Is there any way to make this tailrecursive?
More interesting than this unnatural obsession with tailrecursion
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 tailrecursion until you can get a
sufficiently good "gut feeling" for maximal recursion depths.
 The next step, i guess, would be to write a macro
 withallpermutations, 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 toplevel call, and default
to some innocuous function like identity.
#:Erik

If this is not what you expected, please alter your expectations.