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

Carl Eastlund wrote:
> On Thu, Nov 11, 2010 at 12:18 PM, Neil Toronto <neil.toronto at 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