Hello --

On Sat, 4 Aug 2001, Kero van Gelder wrote:

> >    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

Would you believe... the thing I *meant* to post was:

  class Array
    def my_shuffle!
      size .downto 1 do |n| push delete_at rand(n) end
      self
    end
  end

:-)

At least, that's the one I came up with a few months ago when I was
messing around with this.  Still subject to mathematical scrutiny....
but it's different from that other one, which I *thought* was a
correct reconstruction from memory.

I also did a Ruby translation of the Fisher-Yates shuffle in perlfaq4:

  def fys
    (size - 1) .downto 1 do |i|
      j = rand(i + 1)
      self[i], self[j] = self[j], self[i]
    end
    self
  end

which is similar to yours though not identical.

The benchmarks I did were of those two.  I found that the first one
was much faster for arrays up to about size 1500, then they converged
around 1750, then the Fisher-Yates was faster.


David

-- 
David Alan Black
home: dblack / candle.superlink.net
work: blackdav / shu.edu
Web:  http://pirate.shu.edu/~blackdav