Fisher-Yates (Knuth) Shuffle

The Fisher-Yates Shuffle is an efficient algorithm for randomly shuffling a finite set of items, such as an array or list. It ensures that each possible permutation of the items is equally likely, making it a fair and unbiased method for randomization.

The Fisher–Yates Shuffle is named after Ronald Fisher and Frank Yates, who first described it in their book, "Statistical tables for biological, agricultural and medical research," published in 1938. It is also known as the Knuth Shuffle after Donald Knuth, who popularized the algorithm for computer programming use by including it in his book, "The Art of Computer Programming."

How It Works

The original method described by Fisher and Yates was a manual process where a person would write down a list of numbers from 1 through N, then pick a random number between one and the number of remaining numbers, strike out the number at the random number position, and then write that struck number at the end of a separate list. The person would then repeat the steps (excluding the first step of writing the list of numbers), until all the numbers had been struck out. The numbers written down in the separate list is the resulting random permutation of the original list of numbers.

For computer programming, the steps are basically the same.

Start from the last element of the collection and move backwards.
For each element at index i, pick a random index j such that 0 ≤ j ≤ i. (Note that this uses a collection with a zero-based index.)
Swap the elements at positions i and j.
Repeat until the first element.

JavaScript Example


function fisherYatesShuffle(arr) {
    for (let i = arr.length - 1; i > 0; i--) {
        // Pick a random index from 0 to i
        const j = Math.floor(Math.random() * (i + 1));

        // Swap arr[i] with arr[j]
        [arr[i], arr[j]] = [arr[j], arr[i]];
    }
    return arr;
}

// Example usage
const numbers = [1, 2, 3, 4, 5];
console.log("Original:", numbers);

const shuffled = fisherYatesShuffle([...numbers]); // copy array to preserve original
console.log("Shuffled:", shuffled);