From: "Mauricio Fernández" <mfp@...>
Date: 2005-12-04T10:04:00+09:00
Subject: Re: need some Ruby magic

On Sun, Dec 04, 2005 at 08:48:11AM +0900, Jim Weirich wrote:
> reinder wrote:
> >> my_array.sort_by { rand }
> > 
> > A quick test seems to indicate that this works with the ruby 1.8.2
> > implementation on my Mac. However, there is no guarantee that this call
> > will select each of the n! permutations with equal probability.
> 
> Actually, it will.  sort_by uses a Schwartzian transform to do the 
> sorting.  That means that rand is only called once for each element of 
> the array.  As long as rand gives a decent distribution of random 
> numbers, the permutation will be random too.

sort_by{ rand } is actually biased, since sort_by will preserve the
relative order of the elements for which rand() returned the same value.

%w[a b c d].sort_by{ 0 }                           # => ["a", "b", "c", "d"]
i = 0
%w[a b c d].sort_by{ 10 - (i += 1) / 2 }           # => ["d", "b", "c", "a"]

This means that permutations preserving the relative order of one (or
more) pair of elements of the original array are a bit more probable.

In praxis, the bias this introduces is often so small that the mere
succinctness of sort_by{ rand } more than makes up for it.

-- 
Mauricio Fernandez