"Steven E. Harris" seharris@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