Beefy Boxes and Bandwidth Generously Provided by pair Networks
Your skill will accomplish
what the force of many cannot
 
PerlMonks  

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?
in thread Fisher-Yates theory

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

Log In?
Username:
Password:

What's my password?
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 studying the Monastery: (3)
As of 2020-05-27 00:57 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    If programming languages were movie genres, Perl would be:















    Results (152 votes). Check out past polls.

    Notices?