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