From: Kero van Gelder <kero@...4050.upc-d.chello.nl>
Date: 2001-08-04T23:18:04+09:00
Subject: [ruby-talk:19135] Re: Array.shuffle

>    class Array
>      def my_shuffle!
>        size.times do
> 	 push slice! rand(size)
>        end
>        self
>      end
>    end
> 
> (Maybe some mathematician could check this for correctness :-) It
> actually runs pretty fast for non-huge arrays, if I'm remembering some
> old benchmark results correctly.)

It is slightly off.

Example: size of array is 3, so the number of permutations is 6
The algorithm picks 1 out of 3, 3 times, that's 27 possibilities.
Unfortunately, 27 % 6 != 0

Solution (including speedup):

  class Array
    def shuffle!
      size.downto(2) do |i|
	r = rand(i)
        tmp = self[i-1]
        self[i-1] = self[r]
        self[r] = tmp
      end
      self
    end
  end



+--- Kero ------------------------------ kero@chello.nl ---+
|  Don't split your mentality without thinking twice       |
|                          Proud like a God -- Guano Apes  |
+--- M38c ------- http://members.chello.nl/~k.vangelder ---+