FisherYatesKnuth

FisherYatesKnuth, commonly referred to as the Fisher–Yates shuffle or the Knuth shuffle, is an algorithm for generating a random permutation of a finite sequence. It is an in-place procedure, rearranging the input without extra storage, and it aims to produce every permutation with equal probability. The algorithm is named after Ronald A. Fisher and Frank Yates, with its technique popularized by Donald Knuth.

The standard implementation works by iterating over the sequence from the end toward the beginning. For each position i from n−1 down to 1, it selects a random index j with 0 ≤ j ≤ i and swaps the elements at i and j. An equivalent variant iterates i from 0 to n−2 and chooses j uniformly from i to n−1, performing the same exchange. Both variants are mathematically equivalent and produce a uniform random permutation when the random numbers are unbiased.

The algorithm runs in linear time, O(n), and uses constant extra space, O(1). It requires a source of randomness; the shuffle's correctness hinges on the randomness being uniform. If a modulo operation is used to fit random numbers into a range, care must be taken to avoid bias, or one may employ rejection sampling or a library function that yields unbiased integers in the desired range.

Naming and usage: the term FisherYatesKnuth reflects the combined attribution; many libraries reference either Fisher–Yates or Knuth shuffle. It is widely used to shuffle arrays, lists, and other sequences in programming languages such as Python, JavaScript, and Java.