From: Neil Toronto (neil.toronto at gmail.com) Date: Thu Nov 11 13:16:39 EST 2010 Previous message: [racket-dev] How about adding this simple list-shuffling procedure to racket? Next message: [racket-dev] How about adding this simple list-shuffling procedure to racket? Messages sorted by: [date] [thread] [subject] [author]

```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)])
(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

```

 Posted on the dev mailing list. Previous message: [racket-dev] How about adding this simple list-shuffling procedure to racket? Next message: [racket-dev] How about adding this simple list-shuffling procedure to racket? Messages sorted by: [date] [thread] [subject] [author]