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

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