[Small-cl-src-discuss] Re: [Small-cl-src] combinations and permutations (was: Small, occasionally handy piece of code)

[Ingvar]

> "Steven E. Harris" <seharris at raytheon.com> writes:
> 
> > I wrote one a while ago that may cons less because it requires use
> > of vectors to represent the sequences.
> 
> Following up to myself, if you're interested, I also have similar code
> to produce permutations from a source vector, though the permutation
> algorithm operates destructively in-place on the source sequence.
> 
> It's been about six months since I was doing the analysis for this
> code, but I recall some interesting interdependencies between
> combinations and permutations. Unfortunately my notes are at home
> right now.

An interesting variation for generating the Nth permutation of a list L is:

(defun excise (number args)
  (declare (type fixnum number))
  (cond ((<= number 0) (cdr args))
	(t (cons (car args) (excise (1- number) (cdr args))))))

(defun permute (list num &optional accumulator)
  (if (null list)
    (nreverse accumulator)
    (let* ((length (length list))
	   (nth (mod num length))
	   (remainder (rem num length)))
      (permute (excise nth list) remainder (cons (nth nth list) accumulator)))))

* (loop for n from 0 to 5 collect (permute '(1 2 3) n))

((1 2 3) (2 3 1) (3 1 2) (1 2 3) (2 3 1) (3 1 2))

So far, the only piece of code where I've needed to generate one of all 
possible permutations for a list has been in a Mandelbrot generator, where I 
use that for a recursive call to generate smaller and smaller squares on the 
screen, ignoring to recurse if and only if the sides of the square end up 
having the same iteration depth before heading for infinity, thus making the 
whole process somewhat more pleasurable to watch (I *think* that is in the 
Mandelbrot generator among the SB-CLX demos).

//Ingvar