need some Ruby magic

[Michael Ulm]

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: (e-mail address removed)
Visit our Website: www.isis-papyrus.com

 

[Brian Schröder]

Why not
a.dup.sort { 2*rand(12345) <=3D> 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) <=3D> 2 * rand(12345) + 1}

[snip]

and then he should do us a favour and write

a.sort { [-1, 1][rand(2)] }

instead, which gives the same skewed results but at least does not do
it as complicated.

Brian

 

[Martin DeMello]

This is really just meant to be a simple hack. I think a better
algorithm could assign a random index to each element, then sort on
those indices.

http://www.rubygarden.org/ruby?ArrayShuffle is a variant of your code,
with a nice proof that it's unbiased.

http://c2.com/cgi/wiki?LinearShuffle has a lot of discussion on
shuffling algorithms.

martin

 

[Stephen Waits]

http://www.rubygarden.org/ruby?ArrayShuffle is a variant of your code,
with a nice proof that it's unbiased.

http://c2.com/cgi/wiki?LinearShuffle has a lot of discussion on
shuffling algorithms.

Thanks Martin!

--Steve