From: Daniel Martin <martin@...>
Date: 2006-06-20T12:08:42+09:00
Subject: Re: Is it more convenient to have a random_each in ruby stdlib?

Quoting Matthew Smillie <M.B.Smillie@sms.ed.ac.uk>:

> On Jun 19, 2006, at 9:08, Kroeger, Simon (ext) wrote:
>> I think it's a little bit to simple to be put in the standard lib.
>>
>> a.sort_by{rand}.each {|e| print e , ' '}
>
> But it turns out to not be that simple.  This can give a biased sort
> depending on the underlying sort algorithm, and it's not as efficient
> as it could be, as Alex observes:
<<SNIP>>
> Like a lot of simple-sounding problems, this one's already been
> solved, see:
>
> http://www.nist.gov/dads/HTML/perfectShuffle.html
>
> The linked Haskell implementation also gives a very thorough
> discussion, including a demonstration of how a stable sorting
> algorithm will yield biased results.

Note that the discussion there does not apply to the implementation 
quoted, but
rather to this implementation:

a.sort_by{rand(a.size)}.each {|e| print e , ' '}

which I think we can all see the problem with.  Absent any collisions in the
values chosen by rand each time through the block, the short implementation
quoted above is unbiased.  It's still less effecient than a Fisher-Yates
shuffle (at least in big-O notation; as a practical matter, I'd need to see
some benchmarks), but "biased" is not a critique that can be fairly leveled
against this implementation.  (unless you're willing to accept that your F-Y
shuffle is "biased" too, because for example rand(7) doesn't return 0 with
/exactly/ one-seventh probability, but rather with a probability that's merely
very, very close to one-seventh)

--
@/=map{[/./g]}qw/.h_nJ Xapou cets krht ele_ r_ra/;
map{y/X_/\n /;print}map{pop@$_}@/for@/