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

Co je náhodné promíchání seznamu?

Náhodné promíchání seznamu je nástroj, který vezme seznam položek a uspořádá je do nového, náhodného pořadí. Zadejte jména, úkoly nebo cokoli jiného, vždy jednu položku na řádek, a nástroj je přeuspořádá tak, aby každé možné pořadí mělo stejnou šanci. Tento nástroj používá Fisherův–Yatesův algoritmus, známý algoritmus pro vytváření nezaujatých náhodných pořadí.

Jak používat náhodné promíchání seznamu

1. Zadejte nebo vložte seznam do pole, jednu položku na řádek.
2. Klikněte na „Randomize List“. 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 „Randomize List“.
5. Kliknutím na „Copy Result“ zkopírujete nové pořadí, kliknutím na „Clear“ 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 Fisherův–Yatesův algoritmus promí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 algoritmu

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šší metoda — vybrat dvě náhodné pozice a prohodit je, přičemž se to několikrát opakuje — vypadá náhodně, ale náhodná není. Některé rané programy pro promíchávání z 1950. let fungovaly tímto způsobem a nenápadně upřednostňovaly některá pořadí před jinými, přestože při jediném spuštění nevypadaly podezřele. Fisherův–Yatesův algoritmus se tomuto problému vyhýbá, protože každá položka se přesune právě jednou na pozici vybranou z přesně se zmenšující množiny možností, díky čemuž jsou všechna konečná pořadí stejně pravděpodobná.

Odkud Fisherův–Yatesův algoritmus pochází?

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

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é?

Závisí na generátoru pseudonáhodných čísel (PRNG) webového prohlížeče, což je vzorec vytvářející posloupnosti čísel, které se pro praktické účely chovají jako náhodné. To stačí pro pořadí ve třídě, nasazení do turnaje nebo výběr filmu. Není určen pro kryptografii, hazardní systémy ani pro situace, kdy na nepředvídatelnosti závisí peníze nebo bezpečnost; k tomu jsou zapotřebí 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 „Randomize List“ 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é.