in reply to FisherYates theory
In addition to what sauoq wrote:
I'm not convinced that the FisherYates shuffle actually has very much theory with regard to random order involved at all.
On the surface, each array entry has the appearance of being given a single opportunity at being swapped with another array entry. In practice, array entries nearer to the beginning of the array have additional opportunities of being swapped (as a result of later swaps), meaning that less shuffling happens at the end of the array than at the beginning.
One could argue in great length whether additional shuffling in the array improves the randomness, or whether it produces patterns in the longer term, but it isn't difficult to argue that regardless of which conclusion is valid, the fact that the entries nearer to the beginning have additional chances of being shuffled, while entries nearer the end have fewer chances, that *one* of these ends will be improved more than the other, therefore the algorithm is not optimal.
UPDATE: See node FisherYates theory... does this prove that it is invalid? for my 'proof' that FisherYates weights the results.
Re: FisherYates theory
by AbigailII (Bishop) on Jul 24, 2003 at 08:04 UTC

I'm not convinced that the FisherYates shuffle actually has very much theory with regard to random order involved
at all.
Well, you are wrong. The first publication of the FisherYates
shuffle dates from 1938. It's example 12 in the book
Statistical Tables, whose authors are R.A. Fisher
and F.Yates.
It was also discussed by R. Durstenfeld, in 1964.
Communications of the ACM, volume 7, pp 420.
And of course Donald Knuth mentions it, in Volume 2 of
The Art of Computer Programming. In the third
edition, it's algorithm P, section 3.4.2 on page 145.
Abigail
 [reply] 

++
If there was ever a node that deserves to make the Best Nodes, that's it...
I bookmarked it so I can read that article from ACM's digital library.
UPDATE: I read the paragraph in the ACM digital library, for algorithm 235. How did you ever find that citation? It is the algorithm, but he doesn't credit FisherYates...

Mike
 [reply] 

You have to ask Knuth that question. I got both the FisherYates, and the ACM citation from Knuth.
Abigail
 [reply] 


UPDATE: As pointed out by others, I made an error when translating the code. See their summaries for good explanations. Cheers, and thanks everyone. (tail between legs)
In a previous article, I was challenged for doubting the effectiveness of the FisherYates shuffle as described in perlfaq.
Below, I have written code that exhausts all possible random sequences that could be used during a particular FisherYates shuffle. Statistically, this should be valid, as before the shuffle begins, there is an equal chance that the random sequence generated could be 0 0 0 0 0 as 0 1 2 3 4 as 4 4 4 4 4. By exhaustively executing the FisherYates shuffle, and calculating the total number of occurrences that each result set is produced, we can determine whether the FisherYates shuffle has the side effect of weighting the results, or whether the shuffle is truly random, in that it should be approximately well spread out.
my $depth = 5;
my %results;
sub recurse
{
if (@_ >= $depth) {
my @deck = (1 .. $depth);
shuffle(\@deck, [@_]);
$results{join('', @deck)}++;
} else {
recurse(@_, $_) for 0 .. ($depth1);
}
}
sub shuffle
{
my($deck, $rand) = @_;
my $i = @$deck;
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{$_}, $_;
}
With the above code, I was able to determine that with a deck size of 5, and an initial set of 1 2 3 4 5, there is three times the probability that the resulting set will be 3 1 2 5 4 than the probability that the resulting set will be 2 3 4 5 1. To me, this indicates that this theory is flawed.
If anybody needs to prove to themselves that the test is exhaustive, print out "@$rand" in the shuffle subroutine.
Please analyze the code carefully, pull out your school books, and see if I have made a mistake.
Cheers,
mark  [reply] [d/l] 

Hi MarkM,
That algorithm shows the possible results of a biased shuffle, not a FisherYates 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";
# predecrement $i instead of post  the last would be a noop 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 ;):
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.  [reply] [d/l] [select] 

my $j = shift @$rand;
is no way equivalent to this line from the FAQ implementation
my $j = int rand ($i+1);
The latter picks a swap partner for the current value of $i, randomly between 0 and $i1. I can't quite wrap my brain around what your code is doing here, but it isn't even vaguely equivalent.
Therefore you are not testing a FisherYates shuffle, but some shuffle algorithm of your own invention, which you succeed in proving isn't as good as the FisherYates.
You might find this post Re: When the Best Solution Isn't that does a statistical analysis of several shuffle routines, a FisherYates amongst them, including frequency and standard deviation interesting.
Examine what is said, not who speaks.
"Efficiency is intelligent laziness." David Dunham
"When I'm working on a problem, I never think about beauty. I think only how to solve the problem. But when I have finished, if the solution is not beautiful, I know it is wrong." Richard Buckminster Fuller
 [reply] [d/l] [select] 

sub fisher_yates_shuffle {
my $deck = shift; # $deck is a reference to an array
my $i = @$deck;
while ($i) {
print $i, "\n";
my $j = int rand ($i+1);
@$deck[$i,$j] = @$deck[$j,$i];
}
}
Note how $i is decremented on each iteration. Consider how that alters the sequence of possible indices.
Once you take that into account you get the textbook behaviour.
sub fixed_fisher_yates_shuffle {
my ($deck, $rand) = @_;
my $i = @$deck;
while ($i) {
my $j = shift @$rand;
@$deck[$i,$j] = @$deck[$j,$i];
}
}
use Set::CrossProduct;
my $i = Set::CrossProduct>new([ [0..4], [0..3], [0..2], [0..1], [0] ]
+);
my %count;
while (my $a = $i>get) {
print "@$a : ";
my @foo = (1,2,3,4,5);
fixed_fisher_yates_shuffle(\@foo, $a);
print "@foo\n";
$count{"@foo"}++;
};
foreach my $key (sort keys %count) {
print $key, " = ", $count{$key}, "\n";
};
 [reply] [d/l] [select] 

Again with the "you are wrong." Why the acerbic and argumentative tone? Up to this point, this appears to be a friendly conversation about their views on the theory, which was informative and interesting.
If someone says they're not convinced, you can't disprove that. One may heap on additional evidence to attempt to convince them, but they may continue to be unconvinced for rational or irrational reasons.
This site often discusses matters of faith. There's no right or wrong about being convinced. "You are wrong" demarks an absolutism, both in passive grammar and in connotation. I prefer a community which demonstrates respect for others' faith and others' opinion.
FisherYates may have been proven effective by way of analyzing the results for uniform potential entropy. It may have been proven by logical analysis of the probabilities on each successive swap. Sharing that evidence is helpful, but I ask politely for everyone to build a constructive community, not one which promotes controversy and arrogance.
 [ e d @ h a l l e y . c c ]
 [reply] 

Again with the "you are wrong." Why the acerbic and argumentative tone?
For an opposite view: IMO we dont have enough people like AbigailII kicking around the monastery. Yeah sure he's inclined to be a curmudgondy git with minimalist sense of humour, but hes also a prolific poster who knows the subject matter extremely well. (We have both kinds, but rarely both at the same time ifyswim) If putting up with a bit of crunchyness is what is needed to have AbigailIIs wisdom and knowledge added to the Monestary trove then so be it.
This site often discusses matters of faith. There's no right or wrong about being convinced.
Sure we do discuss matters of faith here quite often. But I personally see a big difference between arguing about which editor is best and whether there is a solid theoretical foundation to what is a mathematical process. AbigailII knows this stuff as well or better than anybody else here who can be bothered to post. He cites his sources, and he speaks his mind.
I fail to see how you can fault him on it. (And ive been in his gunsights getting my shit sorted so dont think that I havent found his manner on occasion to be harsh. But bottom line Id believe what he says over just about anybody else here. I might not agree with him on all things but hes one of the people I come to read.)
Sharing that evidence is helpful, but I ask politely for everyone to build a constructive community, not one which promotes controversy and arrogance.
I think you should develop slightly thicker skin and not fight other peoples battles for them. If MarkM felt his reply was OTT then im sure he would say. (And that argument doesnt apply to this reply at all as you brought up the community and hence gave me the right to respond.)
Cheers, (And I mean that honestly and friendly)

demerphq
_{<Elian> And I do take a kind of perverse pleasure in having an OO assembly language...
}
 [reply] [d/l] 
Re: Re: FisherYates theory
by jsprat (Curate) on Jul 24, 2003 at 08:30 UTC

On the surface, each array entry has the appearance of being given a single opportunity at being swapped with another array entry. In practice, array entries nearer to the beginning of the array have additional opportunities of being swapped (as a result of later swaps), meaning that less shuffling happens at the end of the array than at the beginning.
That is what intuition says, but in this case intuition falls short of reality. A FisherYates shuffle avoids (not introduces) bias by making the pool smaller for each iteration. There are n! possible permutations of a set of n items. After the first iteration, an FY shuffle gives n possible outcomes, each equally likely. The second iteration yields (n  1) for each of the n possible outcomes, leaving us with n*(n1) possibilities  again equally likely. Follow that to its conclusion, you get n(n1)(n2)...1 possibilities, each equally likely. For an example take a 3 item set. There are 3! (= 6) possible permutations of this set if it is shuffled. The first iteration of the loop, there are three possibilities: a(1 2 3), b(2 1 3), and c(3 2 1). The second iteration only swaps the 2nd and 3rd elements, so for a you have an equal possibility of (1 2 3) and (1 3 2); for b  (2 1 3) and (2 3 1); for c  (3 2 1) and (3 1 2). None of the possibilities are duplicated, each one has a 1/6 chance of being selected.
Iter 1  Iter 2
(1 2 3) > (1 2 3)
> (1 3 2)
(1 2 3) > (2 1 3) > (2 1 3)
> (2 3 1)
(3 2 1) > (3 2 1)
> (3 1 2)
Six possibilities, each equally likely.
Another way to look at it is this: The first element has a 2/3 chance of getting swapped the first time and a 1/2 chance the second  giving it a 1/2 * 2/3 = 1/3 chance of ending up in any given slot. Update: Finally, Re: Re: Re: random elements from array  new twist shows a statistical analysis of a FisherYates shuffle. Whew, I'm done. I hope this wasn't homework  or if it was, Anonymous Monk learned something ;)  [reply] [d/l] 
Re: Re: FisherYates theory
by sauoq (Abbot) on Jul 24, 2003 at 06:31 UTC

One could argue in great length whether additional shuffling in the array improves the randomness, or whether it produces patterns in the longer term,
If your RNG was perfect, additional shuffles would neither improve or degrade the randomness.
but it isn't difficult to argue that regardless of which conclusion is valid, the fact that the entries nearer to the beginning have additional chances of being shuffled, while entries nearer the end have fewer chances, that *one* of these ends will be improved more than the other, therefore the algorithm is not optimal.
Unless neither conclusion is valid (see above) in which case a single shuffle is no better or worse than multiple shuffles and the algorithm is optimal.
In practice, however, our RNGs aren't perfect and you may have a point. I suppose you could resolve it by keeping track of the original indexes of the elements and then apply your map and do a second FY shuffle starting with the previous last and moving backwards to the previous first... still linear in time and space... but I doubt it is worth it. :)
sauoq
"My two cents aren't worth a dime.";
 [reply] 

The biggest problem with shuffling algorithms (not just
FisherYates) is the imperfectness of the RNG. The sequence
of numbers it returns is determined by the seed, and only
by the seed. And if from the seed only 32 bits are being
used, there will be at most 2**32 different sequences.
Which means that for a deck of more than 2 cards, FisherYates
cannot be 'fair', as N! won't be a divisor of any
power of 2. Furthermore, 13! > 2**32, so even if
you shuffle a deck of 13 cards, some permutations will
*never* be selected, no matter how many times you perform
the shuffle.
This was pointed out by R. Salfi: COMPSTAT 1974,
Vienna: 1974, pp 28  35.
See also the documentation of the Shuffle module on CPAN.
Abigail
 [reply] 

One could argue in great length whether additional shuffling in the array improves the randomness, or whether it produces patterns in the longer term,
If your RNG was perfect, additional shuffles would neither improve or degrade the randomness.
It seems that additional "shuffling" is required to prevent
a permutation of the array where there is a correlation
between items that are swapped.
It seems the "additional shuffling" is required.
Consider the shuffling of an array of three items without
the so called "additional shuffling": Starting from the
left:
Initial: abc
1 move: abc bac(1/3) cba(1/3)
2 move: abc(1/6) acb(1/6)
Updated: Per Abigail's criticism of a misstyped table
and obscurity. To clarify:
I take issue with:
On the surface, each array entry has the appearance of being given a single opportunity at being swapped with another array entry. In practice, array entries nearer to the beginning of the array have additional opportunities of being swapped (as a result of later swaps), meaning that less shuffling happens at the end of the array than at the beginning.
One could argue in great length whether additional shuffling in the array improves the randomness, or whether it produces patterns in the longer term, but it isn't difficult to argue that regardless of which conclusion is valid, the fact that the entries nearer to the beginning have additional chances of being shuffled, while entries nearer the end have fewer chances, that *one* of these ends will be improved more than the other, therefore the algorithm is not optimal.
Which seems to say that the possible movement of an already
moved item is a weakness of the algorithm. But an array cannot
be randomly shuffled in place without allowing elements to
be moved more than once.
The idea that the errors of a RNG will more adversely affect
the items to which that RNG is more often applied is an
argument that is more subtle. I reject it out of hand.
If the RNG is incorrect the results will not be random and
we are quibling about how obvious the error is.
This distinction may be very important in practice and there
are practical solutions to get a pseudorandomness that is
okay for varying definitions of okay.
 [reply] [d/l] 

I've no idea what you are trying to argue. I also don't
understand your table of situations. In the first move
of a FisherYates shuffle, the last element is swapped,
so with an initial
A, B, C
after the first move we have one of:
C, B, A
A, C, B
A, B, C
Your table suggests a possible B, C, A after the
first move, but you need at least two swaps to
go from A, B, C to B, C, A.
Abigail  [reply] [d/l] [select] 
Re: Re: FisherYates theory
by gjb (Vicar) on Jul 24, 2003 at 08:06 UTC

IMHO the definition of a "good" shuffle algorithm is that starting from a sequence, each of its permutations has the same probability to be the outcome of the shuffle on that starting sequence.
Many "home grown" algorithms violate this criterion and hence are to be considered, well, bad shuffle algorithms. Fisher & Yates satisfies this criterion however (the proof is left as "homework" to the original poster).
You can have a look at Algorithm::Numerical::Shuffle for references as well as a short discussion.
Just my 2 cents, gjb
 [reply] 

