[racket] on reversing a list by way of sort

From: Eli Barzilay (eli at barzilay.org)
Date: Wed Sep 17 02:44:40 EDT 2014

On Wed, Sep 17, 2014 at 1:53 AM, Daniel Prager
<daniel.a.prager at gmail.com> wrote:
> [Sorry for drawing you further in.]

:)  (Indeed, my main point is that all that random-number stuff is
foreign to me...)

> My take on your 3 points:
> Fisher-Yates is only a few lines, so although not a one-liner, it
> seems reasonable to use it for the better space and time performance.

(It's just time -- the space is the roughly same for both, since sorting
will create an intermediate vector too.)

> I agree that an inside-out version is more apt.
> On my reading the final point is an issue if (random n) has problems
> like modulo bias, but if that's the case surely it is (random n) that
> needs fixing.

It goes into all kinds of arguments that are exactly in that area that
I'm trying to avoid -- but IIUC, it's hard to avoid module-biases, and
the FY use of `random' is particularly nasty since it uses all modulos
in the range of the number of items.  See also the point that the WP
page makes about the size of the random number generator state, and how
it limits the number of different permutations that can be generated.
It looks to me like Racket's state is made of 6 fixnums => 2^192 states,
which still doesn't cover all of the permutations of 52 cards.  I have
no idea if this is correct, if some bias reduces the number of
permutations, or whether all of this is something to worry about...

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

Posted on the users mailing list.