Carl Eastlund wrote:
On Thu, Nov 11, 2010 at 12:18 PM, Neil Toronto <neil.toro...@gmail.com> wrote:
Eric Hanchrow wrote:
I find myself using this all the time; it seems it'd be handy to have
built in.
(define (shuffled list)
(sort list < #:key (lambda (_) (random)) #:cache-keys? #t))
Is the distribution of shuffled lists uniform? That'd be hard to analyze,
since it would depend on the sorting algorithm. I would guess it's not.
(Don't worry if you didn't catch this yourself. It's not exactly
straightforward.)
It should be uniform regardless of algorithm, since #:cache-keys? is
#t. Shouldn't it?
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.
(I mean "proven," too. Distributions are very hard to establish using
test cases.)
Besides that, modern implementations of the Fisher-Yates shuffle are
O(n), and this is O(n log n). Not a huge deal, but Fisher-Yates is
simple enough that it's worth the cost to implement it once.
Neil T
_________________________________________________
For list-related administrative tasks:
http://lists.racket-lang.org/listinfo/dev
