Fisher-Yates shuffle algorithm
The Fisher-Yates shuffling can be called also the Knuth shuffle. Frank Yates and Ronald Fisher originated it for the set generation of a finite permutation. In other words the main idea of such algorithm is the randomly shuffled set.
The basic process
One of the Fisher and Yates shuffling variants is the Sattolo’s algorithm that generates the length of the random cycles. The unbiaseimplemented Fisher’s shuffle means that all permutation is equal. This online gambling algorithm is really efficient and requires little time without any additional space.
The Fisher-Yate’s shuffle process is the same that if you pick in a random form some papers from a hat, one by one until the end. And this numerical manner is provided in the rigorous manner to guarantee the unbiased outcome.
The original method
At first this method was mentioned in 1938 namely by Frank Yates and Ronald Fisher. The title of the book was “Statistical tables for biological, agricultural and medical research”. There were used only a paper and a pencil with calculated random numbers that served as the “random source”. So, the player had to write the set of figures from 1 to X, then to choose some random number. He\she had to count it from the end and strike that picked random number, recording it somewhere. The player had to repeat the step of choosing a number until they all weren’t stuck out. Those records of numbers became the numbers random permutation.
The modern method
The modern method of Fisher-Yates Shuffle is elaborated for the computerized use. Richard Durstenfeld presented it in 1964 as "Algorithm 235: Random permutation". Donald E. Knuth distributed it in the other book as "Algorithm P". These authors didn’t recognize the earlier Fisher’s and Yates’ elaboration, only mentioned once their contribution.
The modern algorithm differs from the originate one. Now it’s not a naïve implementation and doesn’t need a count of the remained numbers. Here you’ll move the end those numbers that were struck out, changing them with the final number that wasn’t struck every time. The complexity of time is reduced in such a way to zero. The new implemented algorithm uses the in-pay shuffle (faro shuffle). It doesn’t produce the array’s copy but shuffles the array’s elements in place. If the shuffled array is large, this is a great advantage.
