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 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;
    }
 }

Původní algoritmus

Popis

Novodobý algoritmus

Popis

Vizualizace

Kód

Doporučujeme