Naključni Mešalnik Seznamov - Brezplačno Spletno Orodje za Naključno Razvrščanje

Kaj je naključni mešalnik seznamov?

Naključni mešalnik seznamov je orodje, ki sprejme seznam elementov in jih razporedi v nov, naključen vrstni red. Vnesite imena, opravila ali kar koli drugega, vsakega v svojo vrstico, orodje pa jih premeša tako, da ima vsak možni vrstni red enako možnost, da se pojavi. To orodje uporablja Fisher-Yatesovo premešanje, dobro znan algoritem za ustvarjanje nepristranskih naključnih vrstnih redov.

Kako uporabljati naključni mešalnik seznamov

1. Vnesite ali prilepite seznam v polje, po en element v vrstico.
2. Kliknite »Naključno premešaj seznam«. Elementi se takoj premešajo.
3. Preberite premešani seznam pod gumbom, oštevilčen v novem vrstnem redu.
4. Za novo, neodvisno premešanje znova kliknite »Naključno premešaj seznam«.
5. Kliknite »Kopiraj rezultat«, da kopirate novi vrstni red, ali »Počisti«, da začnete znova.

Prazne vrstice v vnosu se samodejno odstranijo, zato dodatni prelomi vrstic v rezultatih ne ustvarijo praznih vnosov.

Kako deluje algoritem Fisher-Yatesovega premešanja?

Fisher-Yatesovo premešanje gre skozi seznam enkrat, začne pri zadnjem elementu in se pomika proti začetku. Pri vsakem koraku naključno izbere en element iz dela seznama, ki še ni bil postavljen, in ga zamenja s trenutnim položajem.

Formula Fisher-Yatesovega premešanja

Pri seznamu z n elementi, oštevilčenimi 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

Zanka se izvede n − 1-krat, zato premešanje skupaj traja približno n korakov. Temu pravimo linearni čas, zapisan O(n). Ker algoritem vsak položaj obravnava natanko enkrat in izbira iz vse manjše, natančno določene množice elementov, ima vsaka od n! (n fakulteta: n × (n − 1) × ... × 1) možnih razporeditev enako možnost, da je rezultat.

Primer: premešanje seznama s štirimi elementi

Začnimo s štirimi elementi na položajih od 0 do 3: Apple, Banana, Cherry, Date.

• i = 3: naključni izbor je j = 0. Zamenjamo položaja 3 in 0 → Date, Banana, Cherry, Apple
• i = 2: naključni izbor je j = 2. Zamenjava položaja s samim seboj ne spremeni ničesar → Date, Banana, Cherry, Apple
• i = 1: naključni izbor je j = 0. Zamenjamo položaja 1 in 0 → Banana, Date, Cherry, Apple

Končni vrstni red: Banana, Date, Cherry, Apple.

Pri štirih elementih je 4! = 24 možnih vrstnih redov. Vsak od njih, tudi ta, ima pri posameznem premešanju verjetnost 1 proti 24.

Zakaj preprosto ne bi zamenjali naključnih parov?

Na videz preprostejša metoda — naključno izberemo dva položaja in ju večkrat zamenjamo — je videti naključna, vendar ni. Nekateri zgodnji programi za premešanje iz 1950-ih let so delovali tako in so neopazno dajali prednost nekaterim vrstnim redom pred drugimi, čeprav noben posamezen zagon ni bil videti sumljiv. Fisher-Yatesovo premešanje se temu izogne, ker se vsak element premakne natanko enkrat na položaj, izbran iz natančno določenega in vse manjšega nabora možnosti, zaradi česar je vsak končni vrstni red enako verjeten.

Od kod izvira Fisher-Yatesovo premešanje?

Statistika Ronald Fisher in Frank Yates sta metodo opisala leta 1938 v knjigi statističnih tabel za ročno premešanje pri načrtovanju poskusov. Leta 1964 jo je Richard Durstenfeld prilagodil za računalnike, tako da je bilo mogoče seznam preurediti na mestu, brez potrebe po drugem seznamu za spremljanje preostalih elementov. Donald Knuth je to računalniško različico vključil v svojo knjigo The Art of Computer Programming iz 1969, zato jo včasih imenujemo tudi Knuthovo premešanje. Spletni brskalniki danes uporabljajo isti algoritem.

Pogoste uporabe mešalnika seznamov

• Določanje vrstnega reda, v katerem učenci pri pouku predstavljajo ali odgovarjajo na vprašanja
• Naključno določanje razporeda tekmovanja ali vrstnega reda potez v igri
• Razdelitev skupine v naključne ekipe
• Izbira restavracije, filma ali opravila s kratkega seznama, ne da bi dali prednost kateri od možnosti

Navadno premešanje ni vedno najprimernejša izbira. Če se morajo nekateri elementi pojaviti pogosteje kot drugi, je primernejši uteženi izbor. Če mora biti zagotovljena zastopanost vsake kategorije, je stratificirano vzorčenje primernejše od enega samega naključnega premešanja.

Pogosta vprašanja

Ali je premešanje res naključno?

Zanaša se na psevdonaključni generator števil (PRNG) spletnega brskalnika, formulo, ki ustvarja zaporedja števil, ki se za praktične namene obnašajo kot naključna. To zadostuje za vrstne rede pri pouku, določanje razporeda tekmovanja ali izbiro filma. Ni namenjeno kriptografiji, sistemom za igre na srečo ali čemur koli, pri čemer sta denar ali varnost odvisna od nepredvidljivosti; za to so potrebni certificirani generatorji naključnih števil.

Ali orodje pošlje moj seznam strežniku?

Premešanje samo v celoti poteka v brskalniku z uporabo JavaScripta, zato za preureditev seznama ni potrebna omrežna zahteva. Trenutni seznam se zapiše tudi v spletni naslov strani, zato se pri ponovnem nalaganju ali zaznamku ne izgubi. Če ta naslov kopirate, ga delite z drugimi ali ga znova odprete, potuje seznam z njim, tudi do strežnika, ki pozneje naloži to stran. Če je to pomembno, v seznam ne vnašajte občutljivih podatkov.

Kaj se zgodi s podvojenimi elementi?

Podvojeni elementi se ohranijo. Če se »Sam« v vnosu pojavi dvakrat, se bo dvakrat pojavil tudi v premešanem izpisu, morda na različnih položajih.

Ali je število elementov, ki jih lahko premešam, omejeno?

Orodje nima vgrajene omejitve. Ker premešanje poteka v linearnem času, se tudi dolgi seznami na vsaki sodobni napravi preuredijo v delčku sekunde.

Kako se premešanje razlikuje od razvrščanja?

Razvrščanje uredi elemente po stalnem pravilu, na primer po abecedi, in za enak vhod vedno ustvari enak rezultat. Premešanje uredi elemente naključno in skoraj vsakič ustvari drugačen vrstni red, tudi pri enakem vhodu.

Ali lahko isti seznam premešam več kot enkrat?

Da. Ob vsakem kliku na »Naključno premešaj seznam« se algoritem znova zažene, neodvisno od prejšnjega premešanja. Pri majhnem seznamu se lahko po naključju ponovi isti vrstni red; pri večjem seznamu je to izjemno malo verjetno.