From: Glenn Parker <glenn.parker@...>
Date: 2004-12-18T00:26:38+09:00
Subject: Re: [ANN] rand.rb 0.9: Random access methods for Enumerables

--------------020408010501070609070009
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit

Ilmari Heikkinen wrote:
>> How could you know, there is as much randomness as you want?
> 
> Here's a method for testing bias in array shuffle. I'd be interested in 
> hearing about other approaches to probabilistic testing.. anyone?

Here's an alternative that measures shuffle offsets and visibly shows 
the difference between two shuffle methods.

-- 
Glenn Parker | glenn.parker-AT-comcast.net | <http://www.tetrafoil.com/>

--------------020408010501070609070009
Content-Type: text/plain;
 name="shuffle_test.rb"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
 filename="shuffle_test.rb"

#!ruby

class ShuffleTester
  def reset(size)
    @size = size
    @counts = [].fill(0, 0, @size)
    @stored = 0
  end
  def analyze(array)
    array.each_with_index do |value, index|
      # This is the key metric.  The index is the shuffled position
      # and the value is the starting position.  The difference modulo
      # the array size is the shuffle offset.
      offset = (index - value) % @size
      @counts[offset] += 1
    end
    @stored += 1
  end  
  def test(array_size, test_count, shuffle)
    @shuffle = shuffle
    reset(array_size)
    test_count.times do
      analyze( (1..array_size).to_a.send(shuffle) )
    end
  end
  def summary
    puts "summary for #{@shuffle}"
    min_count = @stored
    max_count = 0
    @counts.each_with_index do |count, index|
      bargraph = "#" * (50 * count / @stored)
      printf "%4d: %6d %s\n", index, count, bargraph
      min_count = count if (min_count > count)
      max_count = count if (max_count < count)
    end
    printf "%4s: %6d\n", "min", min_count
    printf "%4s: %6d\n\n", "max", max_count
  end
end

module Enumerable
  def shuffle1!
    each_index {|j| i = rand(size-j); self[j], self[j+i] = self[j+i], self[j]}
    self
  end

  def shuffle2!
    sort!{rand <=> 0.5}
  end
end

ARRAYSIZE = 20
TESTCOUNT = 10000

tester = ShuffleTester.new
tester.test(ARRAYSIZE, TESTCOUNT, :shuffle1!)
tester.summary
tester.test(ARRAYSIZE, TESTCOUNT, :shuffle2!)
tester.summary

--------------020408010501070609070009--