From: Michael Ulm <michael.ulm@...>
Date: 2005-12-08T00:19:48+09:00
Subject: Re: Shuffling an array, sort_by{rand}'s bias (was Re: need some Ruby magic)

hmassa@gmail.com wrote:

> Why not
>  a.dup.sort { 2*rand(12345) <=> 12345 }
> 
> ? that way, we'd have NO colisions ever.
> 

What you have posted does not avoid collisions.
You probably mean something like

a.sort {2*rand(12345) <=> 2 * rand(12345) + 1}

However, the problem of the  sort {rand<=>rand}
methods are not collisions, but the skewed results
from the algorithm that assumes a consistent
comparison operator. Quoting from an earlier
post of mine:

ar = [0, 1, 2]; result = Hash.new(0)
100000.times {result[ar.sort {rand <=> rand}] += 1}
p result
# => {[2, 1, 0]=>25235,
       [2, 0, 1]=>12285,
       [1, 0, 2]=>12426,
       [0, 1, 2]=>25111,
       [1, 2, 0]=>12468,
       [0, 2, 1]=>12475}

You get basically the same result with your method

HTH,

Michael

-- 
Michael Ulm
R&D Team
ISIS Information Systems Austria
tel: +43 2236 27551-219, fax: +43 2236 21081
e-mail: michael.ulm@isis-papyrus.com
Visit our Website: www.isis-papyrus.com