Miješač nasumičnih popisa - Besplatni mrežni alat za nasumično sortiranje popisa

Što je alat za nasumično miješanje popisa?

Alat za nasumično miješanje popisa uzima popis stavki i preslaguje ih u novi, nasumični redoslijed. Upišite imena, zadatke ili bilo što drugo, svako u zaseban redak, a alat će ih presložiti tako da svaki mogući redoslijed ima jednaku vjerojatnost. Ovaj alat upotrebljava algoritam miješanja Fisher–Yates, dobro poznat algoritam za stvaranje nepristranih nasumičnih redoslijeda.

Kako se upotrebljava alat za nasumično miješanje popisa

1. Upišite ili zalijepite popis u okvir, jednu stavku u svaki redak.
2. Kliknite „Nasumično izmiješaj popis”. Stavke se odmah preslože.
3. Pročitajte izmiješani popis ispod gumba, numeriran prema novom redoslijedu.
4. Ponovno kliknite „Nasumično izmiješaj popis” za novo, neovisno miješanje.
5. Kliknite „Kopiraj rezultat” da biste kopirali novi redoslijed ili „Izbriši” da biste počeli ispočetka.

Prazni se redci u unosu automatski uklanjaju pa dodatni prijelomi redaka neće stvoriti prazne stavke u rezultatima.

Kako funkcionira algoritam miješanja Fisher-Yates?

Miješanje Fisher–Yates prolazi kroz popis jednom, počevši od posljednje stavke i krećući se prema početku. U svakom koraku nasumično odabire jednu stavku iz dijela popisa koji još nije smješten te je zamjenjuje sa stavkom na trenutačnom položaju.

Formula miješanja Fisher-Yates

Za popis od n stavki, numeriranih od položaja 0 do položaja 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

Petlja se izvršava n − 1 puta, pa miješanje ukupno traje približno n koraka. To se naziva linearno vrijeme i zapisuje kao O(n). Budući da algoritam svaki položaj razmatra točno jednom i odabire iz skupa stavki koji se postupno smanjuje na točno definiran način, svaki od n! (n faktorijel: n × (n − 1) × ... × 1) mogućih redoslijeda ima jednaku vjerojatnost da bude rezultat.

Primjer: miješanje popisa od četiri stavke

Počnite s četiri stavke na položajima 0 do 3: Jabuka, Banana, Trešnja, Datulja.

• i = 3: nasumično odabrani položaj je j = 0. Zamijenite položaje 3 i 0 → Datulja, Banana, Trešnja, Jabuka
• i = 2: nasumično odabrani položaj je j = 2. Zamjena položaja sa samim sobom ne mijenja ništa → Datulja, Banana, Trešnja, Jabuka
• i = 1: nasumično odabrani položaj je j = 0. Zamijenite položaje 1 i 0 → Banana, Datulja, Trešnja, Jabuka

Konačni redoslijed: Banana, Datulja, Trešnja, Jabuka.

Za četiri stavke postoji 4! = 24 mogućih redoslijeda. Svaki od njih, uključujući ovaj, ima vjerojatnost 1 prema 24 da će se pojaviti pri bilo kojem miješanju.

Zašto jednostavno ne zamijeniti nasumične parove?

Jednostavnija metoda — odabrati dva nasumična položaja i zamijeniti ih, ponavljajući to nekoliko puta — izgleda nasumično, ali nije. Neki rani programi za miješanje iz 1950-ih radili su na taj način te su neprimjetno davali prednost određenim redoslijedima, iako nijedno pojedinačno izvođenje nije izgledalo sumnjivo. Miješanje Fisher–Yates to izbjegava jer se svaka stavka premješta točno jednom, na položaj odabran iz precizno smanjujućeg skupa mogućnosti, zbog čega je svaki konačni redoslijed jednako vjerojatan.

Odakle potječe miješanje Fisher-Yates?

Statističari Ronald Fisher i Frank Yates opisali su tu metodu u 1938, u knjizi statističkih tablica, za ručno miješanje pri planiranju pokusa. Richard Durstenfeld prilagodio ju je računalima u 1964, kako bi se popis mogao presložiti na mjestu, bez potrebe za drugim popisom koji bi pratio preostale stavke. Donald Knuth uključio je tu računalnu inačicu u svoju knjigu Umijeće programiranja računala iz 1969, zbog čega se ponekad naziva Knuthovo miješanje. Web-preglednici danas upotrebljavaju isti algoritam.

Uobičajene primjene alata za miješanje popisa

• Određivanje redoslijeda kojim učenici izlažu ili odgovaraju na pitanja u razredu
• Postavljanje nositelja u turnirskoj tablici ili određivanje redoslijeda poteza u igri
• Nasumična podjela grupe u timove
• Odabir restorana, filma ili zadatka s užeg popisa bez davanja prednosti ijednoj mogućnosti

Obično miješanje nije uvijek najprikladnije. Ako se neke stavke trebaju pojavljivati češće od drugih, bolje je ponderirano odabiranje. Ako svaka kategorija mora biti zajamčeno zastupljena, stratificirano uzorkovanje prikladnije je od jednog nasumičnog miješanja.

Često postavljana pitanja

Je li miješanje doista nasumično?

Oslanja se na generator pseudonasumičnih brojeva (PRNG) web-preglednika, formulu koja proizvodi nizove brojeva koji se u praktične svrhe ponašaju poput slučajnosti. To je dovoljno dobro za redoslijed izlaganja u razredu, određivanje nositelja u turniru ili odabir filma. Nije namijenjeno kriptografiji, sustavima za kockanje ni situacijama u kojima novac ili sigurnost ovise o nepredvidljivosti; u takvim su slučajevima potrebni certificirani generatori slučajnih brojeva.

Šalje li alat moj popis poslužitelju?

Samo miješanje u cijelosti se izvodi u pregledniku pomoću JavaScripta, pa za preslagivanje popisa nije potreban mrežni zahtjev. Trenutačni se popis također zapisuje u web-adresu stranice pa se ne gubi pri ponovnom učitavanju ili spremanju oznake. Ako se ta adresa kopira, dijeli ili ponovno otvori, popis putuje s njom, uključujući i poslužitelj koji poslije učita tu stranicu. Ako je to važno, ne unosite osjetljive podatke u popis.

Što se događa s duplikatima?

Duplikati se zadržavaju. Ako se „Sam” u unosu pojavi dvaput, i dalje će se dvaput pojaviti u izmiješanom rezultatu, moguće na različitim položajima.

Postoji li ograničenje broja stavki koje mogu izmiješati?

Alat nema ugrađeno ograničenje. Budući da se miješanje izvršava u linearnom vremenu, čak se i dugi popisi na svakom suvremenom uređaju preslože u djeliću sekunde.

Po čemu se miješanje razlikuje od sortiranja?

Sortiranje slaže stavke prema fiksnom pravilu, primjerice abecednim redom, i za isti unos uvijek daje isti rezultat. Miješanje slaže stavke nasumično i gotovo svaki put daje drukčiji redoslijed, čak i uz jednak unos.

Mogu li isti popis izmiješati više puta?

Da. Svaki klik na „Nasumično izmiješaj popis” ponovno pokreće algoritam, neovisno o prethodnom miješanju. Kod malog popisa ponovljeni je redoslijed moguć slučajno; kod većeg popisa postaje iznimno malo vjerojatan.