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