### Trivial uniform shuffling

Leslie Polzer suggested this short and simple code to randomly shuffle a sequence:

(defun seqrnd (seq) "Randomize the elements of a sequence. Destructive on SEQ." (sort seq #'> :key (lambda (x) (random 1.0))))

Associating a random key with the values to shuffle, and sorting on
these keys works well, as long as there aren't too many items
(otherwise, there are birthday paradox issues with the finite
mantissa). Unfortunately, quoting the CLHS on `SORT`

: "There is no
guarantee on the number of times the key will be called." In
particular, the key may be called once/element/comparison; it should
probably be (nearly) referentially transparent.

In this case, calling the key for each comparison reduces the above to
sorting with a random comparison predicate, which is known to not
yield an uniform distribution. For example, in a typical quicksort,
the probability of displacing one of the first elements of an `n`

element
sequence to its end is in `1/2^n`

, not `1/n`

. This is not a purely
hypothetical issue: SBCL's `SORT`

calls key for each comparison, as do
some other implementations, I'm sure. Considering the common case for
key functions (reader functions), the decision makes sense.

So, to actually associate a *single* random key to each element,
something like this could be used:

(defun random-shuffle (sequence) (map-into sequence #'car (sort (map 'vector (lambda (x) (cons x (random 1d0))) sequence) #'< :key #'cdr)))