On Thu, Apr 04, 2002 at 06:12:18PM -0600, [EMAIL PROTECTED] wrote:
> It it a requirement of the Fisher-Yates shuffle that the "randomizing
> window" grow smaller through each iteration? Why not just do:
>
> sub shuffle {
> my $deck = shift;
> my $size = @$deck;
> my ($j, $t);
> for (@$deck) {
> $t = $deck->[$j = int rand $size];
> $deck->[$j] = $_;
> $_ = $t;
> }
> }
>
> This is considerably faster than both versions in my tests, and sidesteps
> most nasty boundary cases.
Clever use of the $_ alias!
But here's a nice way to see that it doesn't work. If the deck has
N cards, there are N! different permutations, and a shuffle must
produce each with equal probability. You are picking a
random number in (1..N) N times, for a total of N^N equally likely
outcomes. In order for for your random numbers to produce each
permutation the same number of times, N! would have to divide N^N
evenly. This is only true for N==2 (in which case, your algorithm
happens to work!).
Andrew
