[plt-scheme] Scheme implementation of Fisher-Yates shuffle

Alas, my technique doesn't create a uniform distribution.


On Sun, Aug 9, 2009 at 10:56 AM, Phil Bewig<pbewig at gmail.com> wrote:
> 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:
>
> (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))))
>
>
> On Sun, Aug 9, 2009 at 12:39 PM, Jon Rafkind <rafkind at cs.utah.edu> wrote:
>>
>> Amit Saha wrote:
>>>
>>> Hello all,
>>>
>>> Here is my Scheme implementation of the "modern" version of the "Fisher
>>> Yates Shuffle" (http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle).
>>> 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 (http://amitksaha.wordpress.com; amitsaha.in at gmail.com)
>>>
>>> ;; 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>
>>>
>> 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.
>> _________________________________________________
>>  For list-related administrative tasks:
>>  http://list.cs.brown.edu/mailman/listinfo/plt-scheme
>
>
> _________________________________________________
>  For list-related administrative tasks:
>  http://list.cs.brown.edu/mailman/listinfo/plt-scheme
>
>



-- 
~jrm