From: ara.t.howard@...
Date: 2005-12-04T10:21:02+09:00
Subject: Re: need some Ruby magic

On Sun, 4 Dec 2005, Mauricio [iso-8859-1] Fern�ndez wrote:

> 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.

does

   %w( a b c d ).sort{ rand <=> rand }

help?

-a
-- 
===============================================================================
| ara [dot] t [dot] howard [at] noaa [dot] gov
| all happiness comes from the desire for others to be happy.  all misery
| comes from the desire for oneself to be happy.
| -- bodhicaryavatara
===============================================================================