in reply to Fisher-Yates theory... does this prove that it is invalid?

in thread Fisher-Yates theory

That algorithm shows the possible results of a *biased* shuffle, not a Fisher-Yates shuffle. The random sequence generated would not be 00000 to 44444, it would be 0000 to 4321 (a five digit shuffle requires 4 iterations - the faq goes 5, but the last never swaps - with each iteration shuffling one less item).

The while loop in `shuffle` needs one less iteration, and a minor adjustment to `recurse` would look like this:

#!/usr/bin/perl use strict; use warnings; my $depth = 4; my %results; sub recurse { if (@_ == $depth) { shift; #discard $num my @deck = (1 .. $depth); shuffle(\@deck, [@_]); $results{join('', @deck)}++; } else { my $num = shift || $depth - 1; # one less element each iteration recurse($num, @_, $_) for 0 .. $num--; } } sub shuffle { my($deck, $rand) = @_; my $i = @$deck; # uncomment the following line # print "@$rand\n"; # pre-decrement $i instead of post - the last would be a no-op in +this case while (--$i) { my $j = shift @$rand; @$deck[$i,$j] = @$deck[$j,$i]; } } recurse; for (sort {$results{$b} <=> $results{$a}} keys %results) { printf "%10d %s\n", $results{$_}, $_; }

Here are the results of the modifications, using 4 elements instead of 5 (only 24 possible permutations instead of 120 - makes the node much more readable ;):

1 4321 1 2143 1 4123 1 2413 1 3421 1 1324 1 4312 1 4231 1 3412 1 1432 1 1423 1 2431 1 2314 1 3214 1 3142 1 1342 1 2134 1 3241 1 1243 1 4213 1 3124 1 4132 1 1234 1 2341

Each possible permutation is shown exactly one time, for a possibility of being selected 1 out of 24 times (assuming a perfect rng).

Makes sense???

**Update:** I followed BrowserUK's link below and in that thread there is a statement that elegantly describes the problem with a biased shuffle (When the Best Solution Isn't), by blakem: "It maps 8 paths to 6 end states". In this case, it's 3125 (5**5) paths to 120 (5!) end states - assuming 5 elements to be shuffled.

Comment onRe: Fisher-Yates theory... does this prove that it is invalid?SelectorDownloadCode