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

From: Jon Rafkind (rafkind at cs.utah.edu)
Date: Sun Aug 9 13:39:20 EDT 2009

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.


Posted on the users mailing list.