|
Re: Fisher-Yates shuffle?
by Abigail-II (Bishop) on Aug 09, 2002 at 11:59 UTC
|
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
Luckely, there is a fix, change the rand($_-1)
to rand($_+1).
Abigail
| [reply]
[d/l]
[select] |
|
|
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] |
|
|
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] |
Re: Fisher-Yates shuffle?
by Abigail-II (Bishop) on Aug 09, 2002 at 11:09 UTC
|
That is a Fisher-Yates shuffle. However, you are relying on
the fact the indices on the RHS of the assignment are evaluated
before the indices on the LHS. Something that might have worked
for every version of Perl, but I don't think it's documented
that the behaviour is garanteed.
Abigail | [reply] |
Re: Fisher-Yates shuffle?
by demerphq (Chancellor) on Aug 09, 2002 at 11:41 UTC
|
While im not sure why you want this to be a one liner
($a=rand $_-1),@values[$_,$a] = @values[$a,$_] for (reverse 1..$#value
+s);
I believe that this resolves Abigail-IIs concern.
Yves / DeMerphq
---
Software Engineering is Programming when you can't. -- E. W. Dijkstra (RIP)
| [reply]
[d/l] |
|
|
I didn't set out to create a one-liner. I set out to shuffle some test data. I found the Fisher-Yates thing and set about working out how the Perl implementation using slices worked (I haven't done much with slices before now), and came up with the one-liner which on casual inspection appeared to work.
Given Abigail's fix for it's failings, I'm happy to use it, with it's dependancy on subscript evaluation order on the basis that if this ever changes, it will break a lot of other code too, so the change should be well announced.
As for "why ... a one-liner", I will turn that around and ask--Why not?--provided it works.
Isn't it the Perlish way?
| [reply] |
|
|
will turn that around and ask--Why not?--provided it works
Well, i suppose there are different answers. One could be speed. A "normal" swap of two variables (using a temp var and three assignments) is faster than list assignment. Another but better argument is maintainability. Consider that the cause of abigail-IIs concern about the LHS/RHS is that of trying to get the code to work without imposing a scoping block of some sort. Also, another effect of trying to get this to work on one line is that you used $a. Now most would tell you to avoid that and $b for various reasons. In your code it doesnt look like it would be a problem, but as the code morphs in the future, perhaps back to a multiline solution maybe that $a will not go away, and then maybe the code will morph so much that the trap im thinking off catches you (or your successor)
But one liners are fun I agree. :-)
Given Abigail's fix for it's failings, I'm happy to use it, with it's dependancy on subscript evaluation order on the basis that if this ever changes, it will break a lot of other code too, so the change should be well announced.
Actually I doubt it would be. Im pretty sure the assumption would be that no one in their right mind would depend on such an undocumented feature. (er, sorry :-)
Anyway, seya,
Yves / DeMerphq
---
Software Engineering is Programming when you can't. -- E. W. Dijkstra (RIP)
| [reply] |
|
|