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.<div>
<br></div><div>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.</div><div><br>
</div><div>See the discussion thread given below for more than you will ever want to know about the subject.</div><br><div class="gmail_quote">On Mon, Sep 13, 2010 at 2:07 PM, David Van Horn <span dir="ltr">&lt;<a href="mailto:dvanhorn@ccs.neu.edu">dvanhorn@ccs.neu.edu</a>&gt;</span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"><div><div></div><div class="h5">On 9/13/10 2:46 PM, Stephen Bloch wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
On Sep 13, 2010, at 1:34 PM, Phil Bewig wrote:<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
Do you know a better way to shuffle a list than to convert it to a<br>
vector, shuffle in place, then convert back to a list? You might look<br>
at this discussion:<br>
<a href="http://groups.google.com/group/comp.lang.scheme/browse_thread/thread/24270db01f684439/e54c99564028efec" target="_blank">http://groups.google.com/group/comp.lang.scheme/browse_thread/thread/24270db01f684439/e54c99564028efec</a>.<br>

The list-vector-list method is O(n); any functional method appears to<br>
be O(n log n).<br>
</blockquote>
<br>
In fact, ANY method to do this (even with a vector) takes Omega(n log n)<br>
time. It needs to be able to produce any of n! different answers, so it<br>
needs to make at least log(n!) decisions, which is Theta(n log n).<br>
Otherwise there wouldn&#39;t be enough leaves on the decision tree.<br>
</blockquote>
<br></div></div>
Doesn&#39;t it make n decisions?  1 decision for each element (the decision being, where does the element go in the shuffled list)?<br>
<br>
   <a href="http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle" target="_blank">http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle</a><br><font color="#888888">
<br>
David</font><div><div></div><div class="h5"><br>
_________________________________________________<br>
 For list-related administrative tasks:<br>
 <a href="http://lists.racket-lang.org/listinfo/users" target="_blank">http://lists.racket-lang.org/listinfo/users</a><br>
</div></div></blockquote></div><br>