Shuffle - náhodné seřazení pole

Pro náhodné seřazení se využívají permutace, protože se žádný prvek neopakuje. Permutaci neaplikujeme na samotné hodnoty, ale na indexy. Lze tak zamíchat klidně pole stringů nebo objektů. Při špatné implementaci ale nemusí být výsledek tak náhodný, jak by se mohlo zdát.

Existující řešení

Některé jazyky funkce pro náhodné seřazení obsahují a nemusíme se o nic starat.

PHP:

$arr = range(1, 10);
// 1 2 3 4 5 6 7 8 9 10
shuffle($arr);
// 2 1 8 9 10 6 3 4 5 7

Python:

import random
x = range(1, 11)
# [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
random.shuffle(x)
# [7, 9, 10, 3, 8, 6, 4, 2, 5, 1]

C++:

// Potřebné hlavičky
#include <algorithm> // std::random_shuffle
#include <vector>    // std::vector
#include <ctime>     // std::time
#include <cstdlib>   // std::rand, std::srand

// Vytvoření, naplnění a zamíchání vektoru
std::vector<int> toShuffle;
for(int i = 0; i < 10; i++{
    toShuffle.push_back(i);
}
std::random_shuffle ( toShuffle.begin(), toShuffle.end() );

Vlastní řešení

Prvně jsem musel řešit zamíchání vlastním kódem v jazyce Go, chybí ale například také v JavaScriptu. Algoritmus složitý není, stačí ale drobná chybička a některé permutace se mohou vyskytovat častěji než jiné, nebo vůbec. Pokud vás to zajímá hlouběji, přečtěte si o algoritmu Fisher–Yates shuffle na Wiki, kde je také popsáno, co se může stát při špatné implementaci.

Popis algoritmu. Vybereme náhodně prvek na indexu <0; n>. n je na začátku nastaveno na délku pole - 1. Poté se snižuje, dokud je větší než 0. Náhodný prvek prohodíme s prvkem na pozici n, poté n snížíme o 1 a opakujeme. Prvky přemístěné na konec se nadále ignorují. Tato verze je je známa jako moderní verze Fisher-Yates algoritmu. Výpočetní složitost je O(n), nikoli O(n^2).

Golang:

func shuffleInts(shuffle []int) {
    rand.Seed(time.Now().UnixNano())
    for n := len(shuffle) - 1; n > 0; n-- {
        j := rand.Intn(n + 1)
        shuffle[n], shuffle[j] = shuffle[j], shuffle[n]
    }
}

JavaScript:

// http://stackoverflow.com/a/6274381/1513087
function shuffle(a) {
    var j, x, i;
    for (i = a.length; i; i-- ) {
        j = Math.floor(Math.random() * i);
        x = a[i - 1];
        a[i - 1] = a[j];
        a[j] = x;
    }
}

// ES2015 (ES6) version
function shuffle(a) {
    for (let i = a.length - 1; i > 0; i--) {
        const j = Math.floor(Math.random() * (i + 1));
        [a[i], a[j]] = [a[j], a[i]];
    }
    return a;
}

Pokud si provedeme výpis, jak pole vypadá v průběhu, uvidíme postupně zaplňující se část, kde se již čísla nebudou měnit (za čarou). Na konci již máme náhodně zamíchané pole. Výše popsaný algoritmus je in-place, protože upravuje původní pole. Existuje ale také algoritmus inside-out, který vytvoří nové pole. Tento algoritmus je na Wiki popsán taky.

indexy     hodnoty  [1 2 3 4 5 6 7 8 9 10 | ]
n:9 j:1 = 10 -  2 : [1 10 3 4 5 6 7 8 9 | 2 ]
n:8 j:6 =  9 -  7 : [1 10 3 4 5 6 9 8 | 7 2 ]
n:7 j:7 =  8 -  8 : [1 10 3 4 5 6 9 | 8 7 2 ]
n:6 j:0 =  9 -  1 : [9 10 3 4 5 6 | 1 8 7 2 ]
n:5 j:1 =  6 - 10 : [9 6 3 4 5 | 10 1 8 7 2 ]
n:4 j:3 =  5 -  4 : [9 6 3 5 | 4 10 1 8 7 2 ]
n:3 j:1 =  5 -  6 : [9 5 3 | 6 4 10 1 8 7 2 ]
n:2 j:2 =  3 -  3 : [9 5 | 3 6 4 10 1 8 7 2 ]
n:1 j:0 =  5 -  9 : [5 | 9 3 6 4 10 1 8 7 2 ]

I když se náhodné zamíchání může zdát jako lehký úkol, při vlastním řešení se může jednoduše stát, že všechny možnosti nebudou mít stejnou pravděpodobnost zobrazení.

---

Obrázky v coveru přejaty z Freepik