[racket] [BULK] Re: Looking for feedback on code style

Fisher-Yates is O(n).  It visits each element once, choosing a random
equal-or-forward element and swapping it with the current element.  And it
is fair in the sense that, given a proper random-number generator, each
permutation of the input is equally likely.

All of the purely-functional methods seem to be O(n log n), except for a
naive method that is O(n^2).  That factor of log n is the price paid for not
fixing the number of elements in advance.

See the discussion thread given below for more than you will ever want to
know about the subject.

On Mon, Sep 13, 2010 at 2:07 PM, David Van Horn <dvanhorn at ccs.neu.edu>wrote:

> On 9/13/10 2:46 PM, Stephen Bloch wrote:
>
>> On Sep 13, 2010, at 1:34 PM, Phil Bewig wrote:
>>
>>  Do you know a better way to shuffle a list than to convert it to a
>>> vector, shuffle in place, then convert back to a list? You might look
>>> at this discussion:
>>>
>>> http://groups.google.com/group/comp.lang.scheme/browse_thread/thread/24270db01f684439/e54c99564028efec
>>> .
>>> The list-vector-list method is O(n); any functional method appears to
>>> be O(n log n).
>>>
>>
>> In fact, ANY method to do this (even with a vector) takes Omega(n log n)
>> time. It needs to be able to produce any of n! different answers, so it
>> needs to make at least log(n!) decisions, which is Theta(n log n).
>> Otherwise there wouldn't be enough leaves on the decision tree.
>>
>
> Doesn't it make n decisions?  1 decision for each element (the decision
> being, where does the element go in the shuffled list)?
>
>   http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle
>
> David
>
> _________________________________________________
>  For list-related administrative tasks:
>  http://lists.racket-lang.org/listinfo/users
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.racket-lang.org/users/archive/attachments/20100913/a8ff2187/attachment.html>