Subject: Re: Q: tail-recursive procedure to generate all permutations of a list
From: Erik Naggum <erik@naggum.net>
Date: 2000/10/04
Newsgroups: comp.lang.lisp
Message-ID: <3179671668484915@naggum.net>

* The Glauber <theglauber@my-deja.com>
| 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.