### Re: Fisher-Yates theory... does this prove that it is invalid?

by jsprat (Curate)
 on Jul 25, 2003 at 01:51 UTC ( #277772=note: print w/replies, xml ) Need Help??

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

Hi MarkM,

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) {
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.

Create A New User
Node Status?
node history
Node Type: note [id://277772]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others wandering the Monastery: (6)
As of 2021-01-27 21:14 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
The STEM quote I most wish I'd made is:

Results (307 votes). Check out past polls.

Notices?