Carl Eastlund wrote:
On Thu, Nov 11, 2010 at 12:40 PM, Neil Toronto <neil.toro...@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
_________________________________________________
For list-related administrative tasks:
http://lists.racket-lang.org/listinfo/dev
