From: Stephen Waits <steve@...>
Date: 2005-12-05T06:20:41+09:00
Subject: Re: need some Ruby magic


On Dec 4, 2005, at 12:32 PM, Kero wrote:

> 1) changes the receiver (use new_arr = self.dup instead)
> 2) definitely has a bias. Look e.g. at an array of length three.  
> You will
>    first swap the first element with 3 possibilities, then the  
> second and so
>    on; you're going through 3**3 possibilities. There are 3! possible
>    permutations, but alas, 3! == 6 is not a perfect divisor of 3**3  
> == 27,
>    thus you have a bias.

Good points, thanks.  How about this?

class Array
   def shuffle
     newarr = self.dup
     2.times do
       self.length.times do |x|
         y = rand(self.length)
         newarr[x], newarr[y] = newarr[y], newarr[x]
       end
     end
     newarr
   end
end

# test code lifted from Jim Weirich's earlier post
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.shuffle
   Score[sorted.join("")] += 1
end

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


[~/Code/private/code/snippets] 382% ./shuffle.rb 100000
abc: 16596
acb: 16394
bac: 16700
bca: 16684
cab: 16841
cba: 16785

0:07.87 seconds, 96.4% CPU


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.

--Steve