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