Fisher-Yatesův algoritmus

Fisher-Yatesův algoritmus (pojmenovaný po Ronaldu Fisherovi a Fanku Yatesovi) slouží k náhodnému promíchání vstupního seznamu. Všechny algoritmem generované permutace se vyskytují se stejnou pravděpodobností.

Původní algoritmus

Původní verze Fisher-Yatesova algoritmu z roku 1938 byla založena na postupném výběru a vyškrtávání prvků z původního seznamu a zápisu vybraných hodnot do seznamu nového (algoritmus vykonával člověk za použití tužky a papíru).

Popis

V každém svém kroku uživatel náhodně zvolí celé číslo n na intervalu \\langle 1,\\; k\\rangle, kde k je počet dosud nevyškrtnutých prvků z prvního seznamu. Poté vždy vyškrtne z tohoto seznamu n-tý dosud nevyškrtnutý prvek a zapíše jej na konec druhého seznamu. Takto postupuje tak dlouho, dokud první seznam obsahuje nevyškrtnuté prvky.

Novodobý algoritmus

Původní procedura je sice šikovná pro ruční zpracování, ale z výpočetního hlediska je nevhodná, jelikož má kvadratickou asymptotickou složitost O(n^{2}). Z tohoto důvodu se obvykle v programech používá modifikovaná in-place verze algoritmu s lineární asymptotickou složitostí O(n).

Popis

Základní myšlenka moderního algoritmu je totožná – náhodný výběr. Procedura v každém svém kroku zvolí číslo n na interavalu \\langle1,\\; m - k\\rangle, kde k je počet již prohozených čísel (počet již uskutečněných iterací algoritmu) a m je délka vstupního seznamu. Prvek na indexu n (indexováno od 1) poté prohodí s prvkem na indexu m-k. Algoritmus po zamíchání všech prvků, tj. n-1 iteracích, terminuje.

Lepší asymptotické chování této verze plyne z toho, že jsou již permutované hodnoty zapisovány na konec seznamu a k dosud neprohozeným prvkům lze tedy přistupovat s konstantní časovou složitostí (původní algoritmus vyžadoval iteraci kvůli již zpracovaným hodnotám).

Vizualizace


Kód

    /**
     * Moderni verze Fisher-Yatesova algoritmu
     * @param array pole indexovane od 0
     */
    function fisherYates(array) 
        for i in <array.length - 1, 1> do 
            index = náhodné číslo z intervalu <0, i)
            prohoď(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;
        }
     }







Doporučujeme

Internet pro vaši firmu na míru