[racket-dev] How about adding this simple list-shuffling procedure to racket?

Carl Eastlund wrote:
> On Thu, Nov 11, 2010 at 12:40 PM, Neil Toronto <neil.toronto at gmail.com> wrote:
>> I don't know. I know that the "run through the list and swap with another
>> random element" algorithms are usually non-uniform, and so are a lot of
>> other things that seem like they'd work. I wouldn't use something that
>> wasn't proven to shuffle uniformly, at least for any serious statistics
>> work.
> 
> But this is not "run through the list and swap with another random
> element".  It's "pick a random, uniform ordering, and then sort based
> on it".  The random keys are chosen per element and cached (hence
> #:cache-keys? #t), not per comparison.

Spanking good point, my good man. I think you're right.

Just for the heck of it, I implemented the array-building version of 
Fisher-Yates and gave it a functional interface:

(define (shuffle lst)
   (cond
     [(empty? lst)  empty]
     [else
      (let* ([n  (length lst)]
             [vec  (make-vector n (first lst))])
        (for ([e  (in-list (rest lst))] [i  (in-range 1 n)])
          (define j (random (add1 i)))
          (vector-set! vec i (vector-ref vec j))
          (vector-set! vec j e))
        (vector->list vec))]))


On my computer, it beats the sort-based shuffle on every list size I 
tried it on: 1, 5, 10, 100, and 1000. (Notably, not by much on length-10 
lists.) It has better asymptotic complexity, so that should hold as the 
list size increases.

Interestingly enough, it looks like O(n log n) is as good as purely 
functional code can get. The sorting version is downright elegant.

(Well, it's not *purely* functional. But the Haskell people have to zip 
the list with random numbers in the Random monad, or some other such 
nonsense.)

Neil T