Welcome to the Monastery | |
PerlMonks |
Re: Fisher-Yates theory... does this prove that it is invalid?by jsprat (Curate) |
on Jul 25, 2003 at 01:51 UTC ( [id://277772]=note: print w/replies, xml ) | Need Help?? |
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:
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.
In Section
Meditations
|
|