Náhodný Mixér Zoznamov - Bezplatný Online Nástroj na Premiešanie Zoznamov

Čo je náhodné premiešanie zoznamu?

Náhodné premiešanie zoznamu je nástroj, ktorý vezme zoznam položiek a usporiada ich nanovo v náhodnom poradí. Zadajte mená, úlohy alebo čokoľvek iné, vždy jednu položku na riadok, a nástroj ich premieša tak, aby každé možné poradie malo rovnakú pravdepodobnosť. Tento nástroj používa Fisherov-Yatesov algoritmus, známy algoritmus na vytváranie nestranných náhodných poradí.

Ako používať náhodné premiešanie zoznamu

1. Zadajte alebo vložte zoznam do poľa, jednu položku na riadok.
2. Kliknite na „Randomize List“. Položky sa okamžite premiešajú.
3. Prečítajte si premiešaný zoznam pod tlačidlom, očíslovaný v novom poradí.
4. Kliknite znova na „Randomize List“ a vytvorte nové, nezávislé premiešanie.
5. Kliknutím na „Copy Result“ skopírujete nové poradie alebo na „Clear“ začnete odznova.

Prázdne riadky vo vstupných údajoch sa automaticky odstránia, takže ďalšie zalomenia riadkov nevytvoria vo výsledkoch prázdne položky.

Ako funguje Fisherovho-Yatesov algoritmus premiešania?

Fisherovo-Yatesovo premiešanie prejde zoznam raz, pričom začne poslednou položkou a postupuje smerom k začiatku. V každom kroku náhodne vyberie jednu položku z časti zoznamu, ktorá ešte nebola umiestnená, a vymení ju za položku na aktuálnej pozícii.

Vzorec Fisherovho-Yatesovho premiešania

Zoznam s n položkami má pozície očíslované od pozície 0 po pozíciu 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

Cyklus sa vykoná n − 1-krát, takže premiešanie trvá celkovo približne n krokov. Nazýva sa to lineárny čas a zapisuje sa O(n). Keďže algoritmus zvažuje každú pozíciu presne raz a vyberá zo zmenšujúcej sa, presne určenej množiny položiek, každé z n! možných poradí (n faktoriál: n × (n − 1) × ... × 1) má rovnakú pravdepodobnosť, že bude výsledkom.

Príklad: premiešanie zoznamu štyroch položiek

Začnime so štyrmi položkami na pozíciách 0 až 3: Apple, Banana, Cherry, Date.

• i = 3: náhodne vybraná pozícia je j = 0. Vymeňte pozície 3 a 0 → Date, Banana, Cherry, Apple
• i = 2: náhodne vybraná pozícia je j = 2. Výmena pozície samej so sebou nič nezmení → Date, Banana, Cherry, Apple
• i = 1: náhodne vybraná pozícia je j = 0. Vymeňte pozície 1 a 0 → Banana, Date, Cherry, Apple

Konečné poradie: Banana, Date, Cherry, Apple.

Pri štyroch položkách existuje 4! = 24 možných poradí. Každé z nich vrátane tohto má pri každom premiešaní pravdepodobnosť 1 z 24, že vznikne.

Prečo jednoducho nevymieňať náhodné dvojice?

Jednoduchšia metóda — vybrať dve náhodné pozície a niekoľkokrát ich vymeniť — vyzerá náhodne, ale nie je. Niektoré prvé programy na premiešanie zo 1950. rokov fungovali týmto spôsobom a nenápadne uprednostňovali niektoré poradia pred inými, hoci žiadne jednotlivé spustenie nevyzeralo podozrivo. Fisherovo-Yatesovo premiešanie sa tomu vyhýba, pretože každá položka sa presunie presne raz na pozíciu vybranú z presne sa zmenšujúcej množiny možností, vďaka čomu je každé konečné poradie rovnako pravdepodobné.

Odkiaľ pochádza Fisherovo-Yatesovo premiešanie?

Štatistici Ronald Fisher a Frank Yates opísali túto metódu v roku 1938 v knihe štatistických tabuliek na ručné premiešanie pri navrhovaní experimentov. V roku 1964 ju Richard Durstenfeld prispôsobil počítačom tak, aby bolo možné zoznam preusporiadať priamo bez potreby druhého zoznamu na sledovanie zostávajúcich položiek. Donald Knuth zahrnul túto počítačovú verziu do svojej knihy The Art of Computer Programming z roku 1969, preto sa niekedy nazýva Knuthovo premiešanie. Webové prehliadače dnes používajú rovnaký algoritmus.

Bežné použitia nástroja na premiešanie zoznamu

• Určenie poradia, v ktorom budú žiaci v triede prezentovať alebo odpovedať na otázky
• Náhodné nasadenie do turnajového pavúka alebo určenie poradia ťahov v hre
• Rozdelenie skupiny do náhodných tímov
• Výber reštaurácie, filmu alebo úlohy z krátkeho zoznamu bez uprednostnenia jednej možnosti

Obyčajné premiešanie nie je vždy vhodné. Ak sa niektoré položky majú objavovať častejšie než iné, vhodnejší je vážený výber. Ak musí byť zaručene zastúpená každá kategória, stratifikovaný výber je vhodnejší než jediné náhodné premiešanie.

Najčastejšie otázky

Je premiešanie skutočne náhodné?

Opiera sa o generátor pseudonáhodných čísel (PRNG) webového prehliadača, teda o vzorec, ktorý vytvára postupnosti čísel správajúce sa na praktické účely ako náhodné. To postačuje na poradie v triede, nasadenie do turnaja alebo výber filmu. Nie je určený na kryptografiu, hazardné systémy ani na situácie, v ktorých od nepredvídateľnosti závisia peniaze alebo bezpečnosť; na tie sú potrebné certifikované generátory náhodných čísel.

Odosiela nástroj môj zoznam na server?

Samotné premiešanie prebieha celé v prehliadači pomocou JavaScriptu, takže na preusporiadanie zoznamu nie je potrebná sieťová požiadavka. Aktuálny zoznam sa zapisuje aj do webovej adresy stránky, takže po obnovení stránky alebo použití záložky sa nestratí. Ak sa táto adresa skopíruje, zdieľa alebo znova otvorí, zoznam sa prenáša spolu s ňou aj na server, ktorý túto stránku neskôr načíta. Ak je to dôležité, nevkladajte do zoznamu citlivé informácie.

Čo sa stane s duplicitnými položkami?

Duplicitné položky zostávajú zachované. Ak sa „Sam“ vo vstupných údajoch nachádza dvakrát, v premiešanom výstupe sa objaví tiež dvakrát, prípadne na rôznych pozíciách.

Existuje limit počtu položiek, ktoré môžem premiešať?

Nástroj nemá zabudovaný žiadny limit. Keďže premiešanie prebieha v lineárnom čase, aj dlhé zoznamy sa na každom modernom zariadení preusporiadajú za zlomok sekundy.

Ako sa premiešanie líši od triedenia?

Triedenie usporadúva položky podľa pevného pravidla, napríklad v abecednom poradí, a pre rovnaký vstup vždy vytvorí rovnaký výsledok. Premiešanie usporadúva položky náhodne a takmer zakaždým vytvorí iné poradie, dokonca aj pri rovnakom vstupe.

Môžem ten istý zoznam premiešať viackrát?

Áno. Každé kliknutie na „Randomize List“ spustí algoritmus znova, nezávisle od každého predchádzajúceho premiešania. Pri malom zozname môže rovnaké poradie vzniknúť náhodou; pri väčšom zozname je to mimoriadne nepravdepodobné.