I asked for the best way to shuffle a list on comp.lang.scheme a few years ago. The discussion went wild; you can see it on Google Groups if you want. After that, I wrote this summary: 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: <pre>(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)))) </pre> 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: <pre>(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)))))))))) </pre> Al Petrofsky proposes this somewhat faster code that first partitions the list randomly, then randomly merges them: <pre>(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))))))))) </pre> If you want, you can always do Perl's omigod Schwartzian transform: <pre>(define (shuffle xs) (map cdr (sort (lambda (x y) (< (car x) (car y))) (map (lambda (x) (cons (random 1.0) x)) xs)))) </pre> 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: <pre>(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)))) </pre> <div class="gmail_quote">On Sun, Aug 9, 2009 at 12:39 PM, Jon Rafkind <<a href="mailto:rafkind@cs.utah.edu">rafkind@cs.utah.edu</a>> wrote: <blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"><div class="im">Amit Saha wrote: <blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"> Hello all, Here is my Scheme implementation of the "modern" version of the "Fisher Yates Shuffle" (<a href="http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle" target="_blank">http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle</a>). I am sharing this with the hope that it may be useful to someone in the community. <code> #lang scheme ;; Fisher-Yates shuffling algorithm in Scheme (plt-scheme) ;; Amit Saha (<a href="http://amitksaha.wordpress.com" target="_blank">http://amitksaha.wordpress.com</a>; <a href="http://amitsaha.in" target="_blank">amitsaha.in</a>@<a href="http://gmail.com" target="_blank">gmail.com</a>) ;; Useful to obtain a random shuffle of a list ;; call with (shuffle <your list>) (define (shuffle deck) (let loop ((n (length deck)) (shuff_deck (list->vector deck))) (if (<= n 1) shuff_deck (begin (set! n (- n 1)) (let* ([rand (random (+ 1 n))] [tmp (vector-ref shuff_deck rand)] ) (vector-set! shuff_deck rand (vector-ref shuff_deck n)) (vector-set! shuff_deck n tmp)) (loop n shuff_deck))))) </code> </blockquote></div> Heres the one I wrote a while ago (define (randomize lst) (let ((v (list->vector lst))) (let loop ((max (sub1 (vector-length v)))) (if (= 0 max) (vector->list v) (begin (let ((place (random max))) (let ((tmp (vector-ref v place))) (vector-set! v place (vector-ref v max)) (vector-set! v max tmp))) (loop (sub1 max))))))) Notable differences are I don't set! the index variable, nor do I pass along the vector in the loop. Otherwise I guess they are about the same.<div><div></div><div class="h5"> _________________________________________________ For list-related administrative tasks: <a href="http://list.cs.brown.edu/mailman/listinfo/plt-scheme" target="_blank">http://list.cs.brown.edu/mailman/listinfo/plt-scheme</a> </div></div></blockquote></div>