From: Jim Weirich <jim@...>
Date: 2005-12-04T08:48:11+09:00
Subject: Re: need some Ruby magic

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.

Here's a little experiment:

-------------------------------------------------
N = (ARGV.shift || 1000).to_i
A = %w(a b c)
Perms = %w(abc acb bac bca cab cba)
Score = Hash.new { |h, k| h[k] = 0 }
N.times do
  sorted = A.dup.sort_by { rand }
  Score[sorted.join("")] += 1
end

Score.keys.sort.each do |key|
  puts "#{key}: #{Score[key]}"
end
-------------------------------------------------

Gives:

  $ ruby sortdist.rb 100000
  abc: 16693
  acb: 16688
  bac: 16752
  bca: 16590
  cab: 16475
  cba: 16802

Thats a pretty good distribution for the number of iterations.

-- Jim Weirich


-- 
Posted via http://www.ruby-forum.com/.