Re: Fisher-Yates shuffle?

The code is, unfortunally, wrong. I made a small test program, that shuffles the array a number of times. You should expect all permutations to appear roughly an equal amount of times. However, for a 4 element array, I only get 2 different outcomes:

#!/usr/bin/perl

use strict;
use warnings 'all';

my %buckets;

my @set = "A" .. "D";

foreach my $run (1 .. 10_000) {
    my @values = @set;
    @values[$_,$a] = @values[$a=rand($_-1),$_] for (reverse 1..$#value
+s);
    $buckets {"@values"} ++;
}

foreach my $key (sort keys %buckets) {
    printf "%4d: %s\n" => $buckets {$key}, $key;
}
printf "%d buckets\n" => scalar keys %buckets;
__END__
4955: B C D A
5045: D C A B
2 buckets
[download]

Luckely, there is a fix, change the rand($_-1) to rand($_+1).

Abigail

Comment on Re: Fisher-Yates shuffle? Select or Download Code

Replies are listed 'Best First'.
Re: Re: Fisher-Yates shuffle? by BrowserUk (Patriarch) on Aug 09, 2002 at 20:49 UTC
It didn't take me long to realise (after I had seen your analysis) that `rand(n)`, when `int`'d, gives me values 0..(n-1). I should have spotted that earlier. It took me a lot longer to understand why it required a changed from `rand($_-1)` to `rand($_+1)` rather `rand($_)` to effect the desired results. Maybe others spotted this right away, but incase anyone who reads this doesn't get it, I'll give my explanation and risk correction. I had thought that what was required for the shuffle to work was to swap the last element with a random choice of the preceeding elements, then the second from last with its preceeding elements and so on. It took me while to realise that you have to allow the last element to also have the possibility of 'swapping with itself' otherwise you exclude 1/n of the possible outcomes. Omitting this possibility for all of the passes (in your testcase) gives 3! possible outcomes rather than 4!. But that led me to wondering why my original code only resulted in 2 outcomes! It took me a while longer to see this resulted from the combination of the `int`'d `rand` and the loop starting at 1 not zero. Meaning that whilst n-1 swaps are performed, 2 of these swaps are always the same. Ie. no randomness involved. So, one swap with a choice of two, and 2 swaps with no choice = 2 possible outcomes. All that said, the most significants thing to come out of this (for me) are your elegantly simple test method. your forcing me to look (hard) and learn. (I suspect your choice of A..D rather than A..C was deliberate?) Thankyou for both.	[reply] [d/l] [select]
Re: Fisher-Yates shuffle? by Abigail-II (Bishop) on Aug 12, 2002 at 09:29 UTC
The main reason I chose 'A' .. 'D' was that 4! == 24, and hence the output of the program would fit a 80x24 window. Abigail	[reply]