From: Mathieu Bouchard <matju@...>
Date: 2002-08-08T01:11:24+09:00
Subject: Re: Coding challenge (on Ruby Garden)


On Wed, 7 Aug 2002, Bill Kelly wrote:
> From: "Christoph" <chr_news@gmx.net>
> > "Bill Kelly" <billk@cts.com> wrote in
> > > class Array   # from http://www.rubygarden.org/ruby?OneLiners
> > >     def shuffle!
> > >       each_index {|j| i = rand(size-j); self[j], self[j+i] = self[j+i],
> > self[j]}
> > >     end
> > > end
> > Note that this one liner does not create an even distribution
> > of shuffles.
> Aiyeee!!!  =)   I'd specifically copied the one from the wiki page
> that claimed to be, "O(N) and non-biased" because I recalled a prior
> discussion about certain solutions . . . er, not being evenly-
> distributed in their shuffelation. :)

Your algorithm chooses any of the n possibilities for element 0, then
chooses any of the n-1 remaining possibilities for element 1, and so on.
There are no duplicates possibilities, and there are
(1..n).inject{|a,b|a*b} possibilities covered. Which is factorial of n.
Which is every possible permutation.

In short, the one above is non-biased, if I'm not mistaken.

And, it occurs to me that the one in Christoph's program is exactly the
same algorithm.

________________________________________________________________
Mathieu Bouchard                       http://artengine.ca/matju