Shuffle - náhodné seřazení pole

10.5.2016 (aktualizováno 11.5.2017) Pavel Tipy & triky, JavaScript, PHP

Náhodné seřazení pole se hodí, jak jej ale vytvořit? Některé programovací jazyky nabízejí připravené funkce, v jiných si ji musíte napsat sami.

Shuffle - náhodné seřazení pole

Pro náhodné seřazení se využívají permutace, protože se žádný prvek neopakuje. Permutaci totiž neaplikujeme na samotné hodnoty, ale na indexy. Díky tomu můžeme zamíchat klidně pole stringů nebo objektů. Náhodně zamíchat pole dokáže každý, výsledný efekt ale nemusí být 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 sám o sobě složitý není, stačí ale drobná chybička, a některé permutace se mohou vyskytovat častěji než jiné, některé naopak 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.

V rychlosti k 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. Prvků přemístěných na konec si již všímat nebudeme. Tato verze je popsána jako moderní verze Fisher-Yates algoritmu, protože 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;
    }
}

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

Přidat komentář

Právě odpovídáte na existující komentář. Zrušit

Komentáře

Novinky z blogu

Do Hyundai na interní prohlídku

Jak jsme zavítali do fabriky Hyundai Dymos v Nošovicích na jednu interní exkurzi. Absolvovali bezpečnostním školením, prošli si výrobní halu a také mohli zkusit vyrobit...

Další články