Shuffle

It is easy to shuffle a vector by stepping through the vector, swapping each element with a forward element (including possibly the element itself) until the next-to-last element is reached. The classic description is given by Knuth in AoCP, Volume 2, Section 3.4.2, Algorithm P:

(define (shuffle v)
  (do ((n (length x) (- n 1))) ((zero? n) v))
    (let* ((r (random n)) (t (vector-ref v r)))
      (vector-set! v r (vector-ref v (- n 1)))
      (vector-set! v (- n 1) t))))

But shuffling a list is harder, because lists don't permit O(1) access to any element except the first. Joe Marshall provides this method of shuffling a list by partitioning it into two pieces deterministically, shuffling them recursively, then merging them randomly:

(define (shuffle xs)
  (if (or (null? xs) (null? (cdr xs))) xs
      (let split ((xs xs) (odd '()) (even '()))
        (if (pair? xs)
            (split (cdr xs) (cons (car xs) even) odd)
            (let merge ((odd (shuffle odd)) (even (shuffle even)))
              (cond ((null? odd) even)
                    ((null? even) odd)
                    ((zero? (random 2)) (cons (car odd) (merge (cdr odd) even)))
                    (else (cons (car even) (merge odd (cdr even))))))))))

Al Petrofsky proposes this somewhat faster code that first partitions the list randomly, then randomly merges them:

(define (shuffle xs)
  (let shuffle ((xs xs) (acc '()))
    (if (null? xs) acc
        (if (null? (cdr xs)) (cons (car xs) acc)
            (let split ((xs xs) (x1 '()) (x2 '()))
              (if (null? xs)
                  (if (null? x1)
                      (split x2 '() '())
                      (shuffle x1 (shuffle x2 acc)))
                  (if (zero? (random 2))
                      (split (cdr xs) (cons (car xs) x1) x2)
                      (split (cdr xs) x1 (cons (car xs) x2)))))))))

If you want, you can always do Perl's omigod Schwartzian transform:

(define (shuffle xs)
  (map cdr
    (sort (lambda (x y) (< (car x) (car y)))
      (map (lambda (x) (cons (random 1.0) x)) xs))))

But the fastest method of shuffling a list is to convert it to a vector, use Knuth's algorithm to shuffle the vector, then convert it back to a list; this algorithm operates in linear time (all the others are n log n), and is very fast despite the two type conversions:

(define (shuffle x)
  (do ((v (list->vector x)) (n (length x) (- n 1)))
      ((zero? n) (vector->list v))
    (let* ((r (random n)) (t (vector-ref v r)))
      (vector-set! v r (vector-ref v (- n 1)))
      (vector-set! v (- n 1) t))))