Paul Khuong mostly on Lisp

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)))