<div dir="ltr">Here's a version of "inside-out" Fisher-Yates that should fit the bill:<div><br></div><div><div><font face="courier new, monospace">(define (fy-shuffle lst)</font></div><div><font face="courier new, monospace"> (define v (list->vector lst))</font></div><div><font face="courier new, monospace"> (for/list ([n (in-range (length lst) 0 -1)])</font></div><div><font face="courier new, monospace"> (let* ([i (sub1 n)]</font></div><div><font face="courier new, monospace"> [j (random n)] </font></div><div><font face="courier new, monospace"> [v_j (vector-ref v j)])</font></div><div><font face="courier new, monospace"> (when (not (= i j))</font></div><div><font face="courier new, monospace"> (vector-set! v j (vector-ref v i)))</font></div><div><font face="courier new, monospace"> v_j)))</font></div></div><div><font face="courier new, monospace"><br></font></div><div>Dan<br></div><div><font face="courier new, monospace"><br></font></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Sep 16, 2014 at 8:22 PM, Eli Barzilay <span dir="ltr"><<a href="mailto:eli@barzilay.org" target="_blank">eli@barzilay.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">On Tue, Sep 16, 2014 at 8:22 AM, Robby Findler<br>
<<a href="mailto:robby@eecs.northwestern.edu">robby@eecs.northwestern.edu</a>> wrote:<br>
> But is fisher-yates is linear time, right? (And probably more<br>
> efficient in practice on larger lists, if not smaller.)<br>
<br>
Yes, but there are more considerations that I had when I did the simple<br>
version. In case anyone wants to tackle this, what I vaguely remember<br>
is:<br>
<br>
* FY is faster, but will require much more than a one-liner, since the<br>
list needs to be copied into a vector, then shuffled in-place, then<br>
copied back. I'm not saying that this will make it slower -- since<br>
sort is doing a vector round-trip anyway; it'll just make it much<br>
heavier than something that is not needed too often, and probably very<br>
rarely with big lists when the differene would matter.<br>
<br>
* Looking at the wikipedia page to refresh myself, there is also an<br>
"inside-out" algorithm that they say is better for creating a shuffled<br>
copy of the input vector. The nice thing in that is that it scans the<br>
source vector in sequence, which means that it could work well to use<br>
it, taking items from the list and putting them into an array that is<br>
then converted back into a list.<br>
<br>
* I vaguely remember something about the problem of using integer random<br>
numbers, which are usually the result of modulo (the WP page talks<br>
about it too). I think that there was some concern about that<br>
possibly leading to some bias in the result somehow. As a result,<br>
since I don't know enough about such issues, I used (random) which has<br>
the additional penalty of allocating floats. IOW, the nice thing<br>
about the current one-liner is that I didn't need to go too deep into<br>
considering such issues, allowing me to keep my ignorance while being<br>
relatively confident in the result not suffering from any bias.<br>
<br>
In any case, this is also a point to consider if anyone wants to<br>
implement FY.<br>
<span class="HOEnZb"><font color="#888888"><br>
--<br>
((lambda (x) (x x)) (lambda (x) (x x))) Eli Barzilay:<br>
<a href="http://barzilay.org/" target="_blank">http://barzilay.org/</a> Maze is Life!<br>
____________________<br>
Racket Users list:<br>
<a href="http://lists.racket-lang.org/users" target="_blank">http://lists.racket-lang.org/users</a><br>
</font></span></blockquote></div><br><br clear="all"><div><br></div>-- <br><div dir="ltr"><div style="font-family:arial;font-size:small"><b>Daniel Prager</b></div><div style="font-family:arial;font-size:small">Agile/Lean Coaching, Software Development and Leadership<br></div><div style="font-family:arial;font-size:small"><font color="#999999">Startup: </font><font color="#000000"><a href="http://www.youpatch.com" target="_blank">www.youpatch.com</a></font></div><div style="font-family:arial;font-size:small"><font color="#999999">Twitter:</font> <a href="https://twitter.com/agilejitsu" style="color:rgb(17,85,204)" target="_blank">@agilejitsu</a> </div><div style="font-family:arial;font-size:small"><font color="#999999">Blog:</font> <a href="http://agile-jitsu.blogspot.com/" style="color:rgb(17,85,204)" target="_blank">agile-jitsu.blogspot.com</a></div></div>
</div>