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.
-
Are you posting in the right place? Check out Where do I post X? to know for sure.
-
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big>
<blockquote> <br /> <dd>
<dl> <dt> <em> <font>
<h1> <h2> <h3> <h4>
<h5> <h6> <hr /> <i>
<li> <nbsp> <ol> <p>
<small> <strike> <strong>
<sub> <sup> <table>
<td> <th> <tr> <tt>
<u> <ul>
-
Snippets of code should be wrapped in
<code> tags not
<pre> tags. In fact, <pre>
tags should generally be avoided. If they must
be used, extreme care should be
taken to ensure that their contents do not
have long lines (<70 chars), in order to prevent
horizontal scrolling (and possible janitor
intervention).
-
Want more info? How to link
or How to display code and escape characters
are good places to start.