The Fisher-Yates shuffle (named after Ronald Fisher and Frank Yates) is used to randomly permute given input (list). The permutations generated by this algorithm occur with the same probability.

Original method

The original version of the Fisher-Yates algorithm, which was published in 1938, was based upon iterative striking out of elements of the input list and writing them down to the second output list (this approach was intended to be performed by a human with a paper and a pencil).

Description

At first the user writes down the input list. At each step he randomly picks a number from interval , where k is a number of elements, which are not struck out yet. Then the user strikes out k-th unstruck number and writes it down to the end of the output list. The user repeats this procedure until the input list contain some unstruck element.

Modern algorithm

The original procedure is simple and suitable for a human usage, but it is computationally inconvenient, because it has a quadratic asymptotic complexity. Hence in modern programs an improved in-place version of the algorithm with linear complexity is used.

Description

The idea of the modern version is analogous to the original procedure – random choice. The algorithm in its each step chooses a number n from interval , where k is a number of already processed elements (number of already performed iterations) and m is the length of the input list. Then the algorithm swaps the element at index n (indexed starting at 1) with an element at index m-k. The algorithm terminates after n-1 iterations (i.e. after possibly swapping all the input elements).

The better performance of the modern version is achieved by placing all the (possibly) swapped elements at the end of the currently processed part of the array. While the original procedure requires an iteration to find the k-th unstruck number ( complexity), the modern algorithm simply accesses the relevant index with constant time complexity.

Visualization

Code

    /**
     * Modern version of Fisher-Yates algorithm
     * @param array array indexed starting at 
     */
    function fisherYates(array) 
        for i in <array.length - 1, 1> do 
            index = random number from interval <0, i)
            swap(array[i], array[index])
           

    /**
     * An improved version (Durstenfeld) of the Fisher-Yates algorithm with O(n) time complexity
     * Permutes the given array
     * @param array array to be shuffled
     */
    public static void fisherYates(int[] array) {
        Random r = new Random();
        for (int i = array.length - 1; i > 0; i--) {
            int index = r.nextInt(i);
            //swap
            int tmp = array[index];
            array[index] = array[i];
            array[i] = tmp;
        }
    } 

    /**
     * An improved version (Durstenfeld) of the Fisher-Yates algorithm with O(n) time complexity
     * Permutes the given array
     * @param array array to be shuffled
     */
    static void FisherYates(int[] array) 
    {
        Random r = new Random();
        for (int i = array.Length - 1; i > 0; i--)
        {
            int index = r.Next(i);
            //swap
            int tmp = array[index];
            array[index] = array[i];
            array[i] = tmp;
        }        
    }

    /**
     * An improved version (Durstenfeld) of the Fisher-Yates algorithm with O(n) time complexity
     * Permutes the given array
     * @param array array to be shuffled
     */
     function fisherYates(array) {
        for (var i = array.length - 1; i > 0; i--) {
            var index = Math.floor(Math.random() * i);
            //swap
            var tmp = array[index];
            array[index] = array[i];
            array[i] = tmp;
        }
     }