[racket-dev] How about adding this simple list-shuffling procedure to racket?

From: Eli Barzilay (eli at barzilay.org)
Date: Thu Nov 11 13:26:47 EST 2010

5 minutes ago, Neil Toronto wrote:
> Carl Eastlund wrote:
> > It's "pick a random, uniform ordering, and then sort based on it".
> > The random keys are chosen per element and cached (hence
> > #:cache-keys? #t), not per comparison.
> Spanking good point, my good man. I think you're right.

It's a very common method, and the classic example of the
decorate-map-strip method that has some perl-guy's name slapped on it

The wikipedia page on FY is pretty decent -- and one concern that I've
encountered in the past is that it's sensitive to what that page calls
"modulo bias".  The decorated version is more robust, especially with
(random) that works at the highest `random' granularity.

(BTW, to compare them you should use some (random 1000) thing to avoid
the fp cost.)

          ((lambda (x) (x x)) (lambda (x) (x x)))          Eli Barzilay:
                    http://barzilay.org/                   Maze is Life!

Posted on the dev mailing list.