Juhuslik loendi segaja - Tasuta võrgutööriist loendi juhuslikuks ümberjärjestamiseks

Mis on juhuslik loendi segaja?

Juhuslik loendi segaja on tööriist, mis võtab üksuste loendi ja paigutab need uude juhuslikku järjekorda. Sisestage nimed, ülesanded või midagi muud, igaüks eraldi reale, ning tööriist korraldab need ümber nii, et igal võimalikul järjekorral on võrdne võimalus tekkida. See tööriist kasutab Fisheri-Yatesi segamisalgoritmi, mis on tuntud kallutamata juhuslike järjekordade loomise algoritmina.

Kuidas kasutada juhuslikku loendi segajat

1. Sisestage loend kasti või kleepige see sinna, üks üksus reale.
2. Klõpsake „Randomize List“. Üksused paigutatakse kohe ümber.
3. Lugege segatud loendit nupu all; üksused on uues järjekorras nummerdatud.
4. Uue, eelmistest sõltumatu segamise jaoks klõpsake uuesti „Randomize List“.
5. Uue järjekorra kopeerimiseks klõpsake „Copy Result“ või algusest alustamiseks „Clear“.

Sisendi tühjad read eemaldatakse automaatselt, seega liigsed reavahetused ei tekita tulemustesse tühje kirjeid.

Kuidas Fisheri-Yatesi segamisalgoritm töötab?

Fisheri-Yatesi segamine läbib loendi ühe korra, alustades viimasest üksusest ja liikudes alguse poole. Igal sammul valib see juhuslikult ühe üksuse loendi veel paigutamata osast ning vahetab selle praegusele kohale.

Fisheri-Yatesi segamise valem

n üksusest koosneva loendi puhul, mille positsioonid on nummerdatud alates positsioonist 0 kuni positsioonini 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

Tsükkel käivitub n − 1 korda, seega kulub segamiseks kokku ligikaudu n sammu. Seda nimetatakse lineaarseks ajakuluks ja tähistatakse O(n). Kuna algoritm käsitleb iga positsiooni täpselt ühe korra ja valib üksusi täpselt määratletud kahanevast kogumist, on kõigil n! (n-i faktoriaal: n × (n − 1) × ... × 1) võimalikul järjekorral tulemuseks saamise tõenäosus võrdne.

Näide: neljast üksusest koosneva loendi segamine

Alustame nelja üksusega positsioonidel 0 kuni 3: Apple, Banana, Cherry, Date.

• i = 3: juhuslikult valitud j = 0. Vahetame positsioonid 3 ja 0 → Date, Banana, Cherry, Apple
• i = 2: juhuslikult valitud j = 2. Positsiooni vahetamine iseendaga ei muuda midagi → Date, Banana, Cherry, Apple
• i = 1: juhuslikult valitud j = 0. Vahetame positsioonid 1 ja 0 → Banana, Date, Cherry, Apple

Lõplik järjekord: Banana, Date, Cherry, Apple.

Nelja üksuse korral on 4! = 24 võimalikku järjekorda. Igal neist, sealhulgas sellel, on iga segamise korral 1 võimalus 24-st.

Miks mitte lihtsalt juhuslikke paare vahetada?

Lihtsamana näiv meetod — valida kaks juhuslikku positsiooni ja vahetada need mitu korda — näib juhuslik, kuid tegelikult ei ole seda. Mõned esimesed segamisprogrammid 1950. aastatel töötasid nii ning eelistasid märkamatult teatud järjekordi teistele, kuigi ükski üksik käivitus ei paistnud kahtlane. Fisheri-Yatesi segamine väldib seda, sest iga üksus liigub täpselt ühe korra positsioonile, mis valitakse täpselt kahanevast valikute hulgast; just see muudab kõik lõplikud järjekorrad võrdselt tõenäoliseks.

Kust Fisheri-Yatesi segamine pärineb?

Statistikud Ronald Fisher ja Frank Yates kirjeldasid seda meetodit 1938 statistiliste tabelite raamatus, et seda saaks katsete kavandamisel käsitsi rakendada. 1964 kohandas Richard Durstenfeld selle arvutitele, nii et loendi sai ümber järjestada kohapeal, ilma et järelejäänud üksuste jälgimiseks oleks vaja teist loendit. Donald Knuth lisas selle arvutiversiooni oma 1969 raamatusse The Art of Computer Programming, mistõttu nimetatakse seda mõnikord Knuthi segamiseks. Veebibrauserid kasutavad tänapäeval sama algoritmi.

Loendi segaja levinud kasutusalad

• Õpilaste ettekannete või klassis küsimustele vastamise järjekorra määramine
• Turniiritabeli koostamine või mängus käikude järjekorra määramine
• Rühma jagamine juhuslikeks võistkondadeks
• Restorani, filmi või ülesande valimine lühinimekirjast ühtki valikut eelistamata

Lihtne segamine ei sobi alati. Kui mõned üksused peavad esinema teistest sagedamini, sobib paremini kaalutud valik. Kui iga kategooria esindatus peab olema tagatud, toimib kihistatud valim paremini kui üks juhuslik segamine.

Korduma kippuvad küsimused

Kas segamine on tõesti juhuslik?

See tugineb veebibrauseri pseudojuhuslike arvude generaatorile (PRNG), valemile, mis tekitab arvujadasid, mis on praktilistel eesmärkidel juhuslike jadadega sarnased. Sellest piisab klassis järjekorra määramiseks, turniiritabeli koostamiseks või filmi valimiseks. See ei ole mõeldud krüptograafia, hasartmängusüsteemide ega olukordade jaoks, kus raha või turvalisus sõltub ettearvamatusest; selleks on vaja sertifitseeritud juhuslike arvude generaatoreid.

Kas tööriist saadab mu loendi serverisse?

Segamine toimub täielikult brauseris JavaScripti abil, seega ei ole loendi ümberjärjestamiseks võrgupäringut vaja. Praegune loend kirjutatakse ka veebiaadressi, mistõttu ei lähe see lehe uuesti laadimisel ega järjehoidja kasutamisel kaduma. Kui see aadress kopeeritakse, jagatakse või avatakse uuesti, liigub loend sellega kaasa, sealhulgas serverisse, mis selle lehe hiljem laadib. Kui see on oluline, vältige loendisse tundliku teabe lisamist.

Mis juhtub korduvate üksustega?

Korduvad üksused säilitatakse. Kui sisendis esineb „Sam“ kaks korda, esineb see segatud väljundis samuti kaks korda, võimalik, et eri positsioonidel.

Kas segatavate üksuste arvul on piirang?

Tööriistal ei ole sisseehitatud piirangut. Kuna segamine toimub lineaarses ajas, järjestatakse ka pikad loendid igas tänapäevases seadmes ümber sekundi murdosa jooksul.

Mille poolest erineb segamine sortimisest?

Sortimine järjestab üksused kindla reegli, näiteks tähestiku, järgi ja annab sama sisendi korral alati sama tulemuse. Segamine järjestab üksused juhuslikult ning annab peaaegu iga kord erineva järjekorra isegi identse sisendi korral.

Kas sama loendit saab segada rohkem kui ühe korra?

Jah. Iga „Randomize List“ klõps käivitab algoritmi uuesti, sõltumatult varasemast segamisest. Väikese loendi korral võib sama järjekord juhuslikult korduda; suurema loendi korral muutub see äärmiselt ebatõenäoliseks.