Fisher–Yates shuffle
The Fisher–Yates shuffle, in its original form, was described in 1938 by Ronald Fisher and Frank Yates in their book Statistical tables for biological, agricultural and medical research.
Fisher and Yates took care to describe how to obtain such random numbers in any desired range from the supplied tables in a manner which avoids any bias.
[5] Neither Durstenfeld's article nor Knuth's first edition of The Art of Computer Programming acknowledged the work of Fisher and Yates; they may not have been aware of it.
[citation needed] Subsequent editions of Knuth's The Art of Computer Programming mention Fisher and Yates' contribution.
If j=3, for example, then one strikes out the third letter on the scratch pad and writes it down as the result: A second random number is chosen, this time from 1 to 7.
The apparently redundant initial assignment to a[i] is there to ensure that the following access to a[j] is not an uninitialized variable in the case that i = j.
In that case, the value copied in the second assignment to a[i] does not matter either, as it is immediately overwritten by the assignment to a[j], but many popular languages (specifically including C and C++, with limited exceptions which do not apply here[8]) state that simply reading an uninitialized value is undefined behavior and thus a programming error.
Assuming the source can be generated procedurally and so takes no space, this requires performing all n iterations to finalize the output, but only k elements of storage.
Another difference is that the regular algorithm needs to know n ahead of time, but not k; it is not necessary to decide in advance how much output is enough.
The reverse algorithm needs to know (an upper bound on) k ahead of time, but not n; it is not necessary to decide in advance how much input is enough.
This simple change modifies the algorithm so that the resulting permutation always consists of a single cycle.
In fact, as described below, it is quite easy to accidentally implement Sattolo's algorithm when the ordinary Fisher–Yates shuffle is intended.
In 1990, Anderson developed a parallel version for machines with a small number of processors accessing shared memory.
[11] The algorithm generates a random permutations uniformly so long as the hardware operates in a fair manner.
Finally, the sorting method has a simple parallel implementation, unlike the Fisher–Yates shuffle, which is sequential.
However, this is very likely to produce highly non-uniform distributions, which in addition depend heavily on the sorting algorithm used.
Randomized comparison functions applied to other sorting methods like merge sort may produce results that appear more uniform, but are not quite so either, since merging two sequences by repeatedly choosing one of them with equal probability (until the choice is forced by the exhaustion of one sequence) does not produce results with a uniform distribution; instead the probability to choose a sequence should be proportional to the number of elements left in it[citation needed].
In principle this shuffling method can even result in program failures like endless loops or access violations, because the correctness of a sorting algorithm may depend on properties of the order relation (like transitivity) that a comparison producing random values will certainly not have.
For instance the fact that any element should compare equal to itself allows using them as sentinel value for efficiency reasons, and if this is the case, a random comparison function would break the sorting algorithm.
Similarly, always selecting j from the entire range of valid array indices on every iteration also produces a result which is biased, albeit less obviously so.
when n > 2 (as the latter is divisible by n−1, which shares no prime factors with n), some permutations must be produced by more of the nn sequences of swaps than others.
As a concrete example of this bias, observe the distribution of possible outcomes of shuffling a three-element array [1, 2, 3].
This is because 16 does not evenly divide 100: the largest multiple of 16 less than or equal to 100 is 6×16 = 96, and it is the numbers in the incomplete range 96–99 that cause the bias.
A method of obtaining random numbers in the required ranges that is unbiased and nearly never performs the expensive modulo operation was described in 2018 by Daniel Lemire.
[20]: FP Multiply (Biased) [22]: 2 The problem here is that random floating-point numbers, however carefully generated, always have only finite precision.
The extra cost of eliminating "modulo bias" when generating random integers for a Fisher-Yates shuffle depends on the approach (classic modulo, floating-point multiplication or Lemire's integer multiplication), the size of the array to be shuffled, and the random number generator used.
[24] It is impossible for a generator with less than 226 bits of internal state to produce all the possible permutations of a 52-card deck.
A further problem occurs when a simple linear congruential PRNG is used with the divide-and-take-remainder method of range reduction described above.
When the divisor is a power of two, taking the remainder essentially means throwing away the high-order bits, such that one ends up with a significantly less random value.
Select Fisher-Yates and change the line to have pre-decrement --m rather than post-decrement m-- giving i = Math.floor(Math.random() * --m);, and you get Sattolo's algorithm where no item remains in its original position.
