Náhodný Mícháč Seznamů - Bezplatný Online Nástroj pro Náhodné Řazení Seznamů

Co je náhodný míchač seznamu?

Náhodný míchač seznamu je nástroj, který vezme seznam položek a uspořádá je znovu v novém, náhodném pořadí. Uživatel zadá jména, úkoly nebo cokoli jiného, jednu položku na řádek, a nástroj je přeuspořádá tak, aby každé možné pořadí mělo stejnou šanci, že vznikne. Nástroj používá Fisherovo–Yatesovo míchání, známý algoritmus pro vytváření nezkreslených náhodných pořadí.

Jak používat náhodný míchač seznamu

1. Zadejte nebo vložte seznam do pole, jednu položku na řádek.
2. Klikněte na „Zamíchat seznam“. Položky se okamžitě přeuspořádají.
3. Přečtěte si promíchaný seznam pod tlačítkem, očíslovaný v novém pořadí.
4. Pro nové, nezávislé promíchání klikněte znovu na „Zamíchat seznam“.
5. Kliknutím na „Kopírovat výsledek“ zkopírujete nové pořadí, kliknutím na „Vymazat“ začnete znovu.

Prázdné řádky ve vstupu se automaticky odstraní, takže nadbytečné konce řádků nevytvoří ve výsledcích prázdné položky.

Jak funguje algoritmus Fisherova–Yatesova míchání?

Fisherův–Yatesův algoritmus projde seznam jednou, začíná poslední položkou a postupuje směrem k začátku. V každém kroku náhodně vybere jednu položku z dosud neumístěné části seznamu a prohodí ji s položkou na aktuální pozici.

Vzorec Fisherova–Yatesova míchání

U seznamu n položek očíslovaných od pozice 0 do pozice n − 1:

1for i from n − 1 down to 1:
2    choose a random whole number j, where 0 ≤ j ≤ i
3    swap the items at positions i and j
4

Smyčka proběhne n − 1krát, takže promíchání zabere celkem přibližně n kroků. Tomu se říká lineární čas, zapisovaný jako O(n). Protože algoritmus zohlední každou pozici právě jednou a vybírá z postupně se zmenšující, přesně vymezené množiny položek, má každé z n! (faktoriál n: n × (n − 1) × ... × 1) možných pořadí stejnou šanci stát se výsledkem.

Příklad: promíchání seznamu čtyř položek

Začněme se čtyřmi položkami na pozicích 0 až 3: Apple, Banana, Cherry, Date.

• i = 3: náhodně vybraná pozice je j = 0. Prohoďte pozice 3 a 0 → Date, Banana, Cherry, Apple
• i = 2: náhodně vybraná pozice je j = 2. Prohození pozice se sebou nic nezmění → Date, Banana, Cherry, Apple
• i = 1: náhodně vybraná pozice je j = 0. Prohoďte pozice 1 a 0 → Banana, Date, Cherry, Apple

Konečné pořadí: Banana, Date, Cherry, Apple.

U čtyř položek existuje 4! = 24 možných pořadí. Každé z nich, včetně tohoto, má při libovolném promíchání pravděpodobnost 1 ku 24.

Proč jednoduše neprohazovat náhodné dvojice?

Jednodušeji vypadající metoda, při které se vyberou dvě náhodné pozice a vymění se, a to se několikrát opakuje, působí náhodně, ale náhodná není. Tak fungovaly některé rané počítačové programy na míchání a nenápadně upřednostňovaly určitá pořadí před jinými, přestože žádný jednotlivý průběh nevypadal podezřele. Fisherovo–Yatesovo míchání se tomu vyhýbá, protože každá položka se přesune právě jednou, a to na pozici vybranou z přesně se zmenšující množiny možností, díky čemuž je každé konečné pořadí stejně pravděpodobné.

Odkud pochází Fisherovo–Yatesovo míchání?

Statistici Ronald Fisher a Frank Yates popsali tuto metodu v roce 1938 v knize statistických tabulek, určené k ručnímu míchání při plánování experimentů. V roce 1964 ji Richard Durstenfeld upravil pro počítače, aby bylo možné seznam přeuspořádat na místě, bez druhého seznamu pro evidenci zbývajících položek. Donald Knuth zařadil tuto počítačovou verzi do své knihy The Art of Computer Programming z roku 1969, a proto se jí někdy říká Knuthovo míchání.

Běžné použití nástroje pro promíchání seznamu

• Určení pořadí, v jakém budou studenti ve třídě prezentovat nebo odpovídat na otázky
• Losování nasazení do turnajového pavouka nebo určení pořadí tahů ve hře
• Rozdělení skupiny do náhodných týmů
• Výběr restaurace, filmu nebo úkolu z užšího seznamu bez upřednostnění některé možnosti

Prosté promíchání není vždy vhodné. Pokud se některé položky mají objevit častěji než jiné, je vhodnější vážený výběr. Pokud musí být zaručeno zastoupení každé kategorie, je lepší stratifikovaný výběr než jediné náhodné promíchání.

Často kladené otázky

Je promíchání skutečně náhodné?

Nástroj využívá generátor pseudonáhodných čísel (PRNG) webového prohlížeče, tedy vzorec, který vytváří posloupnosti čísel chovající se pro praktické účely jako náhodná. To stačí na pořadí ve školní třídě, nasazování do turnaje nebo výběr filmu. Generátor není navržen pro kryptografii, pro sázkové systémy ani pro situace, kdy na nepředvídatelnosti závisejí peníze nebo bezpečnost; ty vyžadují certifikované generátory náhodných čísel.

Odesílá nástroj můj seznam na server?

Samotné promíchání probíhá celé v prohlížeči pomocí JavaScriptu, takže k přeuspořádání seznamu není potřeba síťový požadavek. Aktuální seznam se také zapisuje do webové adresy stránky, takže se při opětovném načtení ani uložení záložky neztratí. Pokud je tato adresa zkopírována, sdílena nebo znovu otevřena, seznam putuje spolu s ní, a to i na jakýkoli server, který později načte danou stránku. Pokud je to důležité, nevkládejte do seznamu citlivé informace.

Co se stane s duplicitními položkami?

Duplicitní položky zůstanou zachovány. Pokud se ve vstupu dvakrát objeví „Sam“, ve výstupu se po promíchání také objeví dvakrát, případně na různých pozicích.

Existuje limit počtu položek, které mohu promíchat?

Nástroj nemá zabudovaný žádný limit. Protože promíchání probíhá v lineárním čase, i dlouhé seznamy se na každém moderním zařízení přeuspořádají za zlomek sekundy.

Jak se promíchání liší od třídění?

Třídění uspořádává položky podle pevného pravidla, například podle abecedy, a pro stejný vstup vždy vytvoří stejný výsledek. Promíchání uspořádává položky náhodně a téměř pokaždé vytvoří jiné pořadí, i když je vstup totožný.

Mohu stejný seznam promíchat více než jednou?

Ano. Každé kliknutí na „Zamíchat seznam“ spustí algoritmus znovu, nezávisle na předchozím promíchání. U malého seznamu se může stejné pořadí náhodou zopakovat; u většího seznamu je to velmi nepravděpodobné.

Reference

1. National Institute of Standards and Technology. Dictionary of Algorithms and Data Structures: Fisher-Yates shuffle. NIST DADS, Fisherovo–Yatesovo míchání — algoritmus vymění každý prvek s náhodným prvkem ze zbývajícího rozsahu a běží v lineárním čase; Fisher a Yates, 1938; Durstenfeld, 1964.
2. MDN Web Docs (Mozilla). Math.random(). MDN, Math.random() — pseudonáhodná čísla v prohlížeči nejsou kryptograficky bezpečná.