CodeKitHubKas yra šis įrankis?
Sąrašo atsitiktinimo generatorius pertvarko elementų rinkinį į atsitiktinę tvarką arba ištraukia iš jo atsitiktinį pogrupį. Sudėtingiausia dalis — tai atlikti be šališkumo: naivus metodas, pavyzdžiui, rikiuoti masyvą atsitiktine palyginimo funkcija, duoda iškreiptą pasiskirstymą, kuriame tam tikros tvarkos yra kur kas labiau tikėtinos nei kitos.
Šis įrankis naudoja Fisher–Yates (Durstenfeld) maišymo algoritmą — standartinį metodą įrodomai vienodai atsitiktinei permutacijai gauti: bet kuri galima jūsų sąrašo tvarka yra vienodai tikėtina.
Kodėl jį naudoti?
- Tikrai nešališkas maišymas — Fisher–Yates, o ne dažnai naudojamas sort(() => Math.random() - 0.5) anti-šablonas, iškreipiantis rezultatus.
- Nugalėtojų rinkimo režimas: ištraukite tiksliai N atsitiktinių elementų vietoje viso sąrašo maišymo — puikiai tinka loterijoms ir dovanų akcijoms.
- Pasirinktinis dublikatų šalinimas prieš maišymą — sąrašams, kuriuose gali būti atsitiktinių pasikartojimų.
- Veikia su bet kokiu tekstu — vardais, užduotimis, bilietais, prizais — po vieną elementą eilutėje.
- Privatu: maišymas vyksta visiškai jūsų naršyklėje, niekas neįkeliama.
Kaip naudoti
- Įklijuokite sąrašą į langą, po vieną elementą eilutėje.
- Jei reikia, pažymėkite "pašalinti dublikatus prieš maišymą", jei sąraše gali būti pasikartojimų.
- Pilnam pertvarkymui tiesiog spauskite Shuffle. Norėdami išrinkti nugalėtojus, pažymėkite N elementų parinktį ir nurodykite, kiek jų ištraukti.
- Nukopijuokite rezultatą — spauskite Shuffle dar kartą, kai tik norite naujos atsitiktinės tvarkos ar naujo traukimo.
Pavyzdys
Įvestis
Alice
Bob
Charlie
Diana
EthanIšvestis
Atsitiktinai pertvarkytas sąrašas, pvz., Charlie, Ethan, Alice, Diana, Bob — kiekvieną kartą spustelėjus Shuffle skirtingas.Nugalėtojų rinkimo režime, nustačius 2, tas pats sąrašas vietoje to gali duoti tik Ethan ir Alice — atsitiktinį 2 elementų traukimą, o ne 2 elementų fragmentą iš vieno sumaišyto sąrašo.
Kodėl naivus maišymas duoda iškreiptus rezultatus
sort(() => Math.random() - 0.5) — dažnai naudojamas triukas, kuris atrodo teisingas, bet toks nėra: jis remiasi tuo, kad rikiavimo algoritmas komparatorių iškviečia tam tikrą skaičių kartų tam tikru šablonu, o realios rikiavimo implementacijos to negarantuoja. Praktinis efektas — maišymas, kuriame tam tikros tvarkos pasitaiko dažniau nei kitos — pakankamai subtiliai, kad nepastebėtum iš karto, bet statistiškai išmatuojama per daug bandymų.
Fisher–Yates apeina visą šią problemą: vietoje to, kad prašytų rikiavimo algoritmo netiesiogiai sukurti atsitiktinumą, jis tiesiogiai sukeičia kiekvieną poziciją su atsitiktine likusia pozicija lygiai vieną kartą — tai įrodomai tolygu, nepriklausomai nuo konkrečios kalbos rikiavimo implementacijos.
Dažniausiai užduodami klausimai
Kodėl nenaudoti tiesiog array.sort(() => Math.random() - 0.5)?
Šis vieno sakinio triukas yra gerai žinomas anti-šablonas: JavaScript sort() negarantuoja, kad kiekviena elementų pora bus palyginta tiek pat kartų, todėl gaunama tvarka pastebimai iškreipta link tam tikrų permutacijų — kai kurie elementai dažniau atsiranda arti pradžios ar pabaigos, nei būtų tikrai atsitiktiniu atveju. Fisher–Yates to visiškai išvengia dėl savo sandaros, ir būtent šį algoritmą realiai naudoja šis įrankis.
Ar maišymo tvarka tikrai nešališka?
Taip. Fisher–Yates eina per sąrašą vieną kartą, ir kiekviename žingsnyje sukeičia dabartinį elementą su tolygiai atsitiktinai parinktu elementu iš likusios nesumaišytos dalies. Matematiškai įrodyta, kad tai duoda kiekvieną galimą tvarką su vienoda tikimybe, jei atsitiktinumo šaltinis geras (JavaScript Math.random()).
Kuo skiriasi maišymas nuo nugalėtojų rinkimo režimo?
Maišymo režimas pertvarko kiekvieną sąrašo elementą ir parodo juos visus, tik naujoje tvarkoje. Nugalėtojų rinkimo režimas ištraukia tik N atsitiktinių elementų ir parodo tik juos — naudinga, kai norite išrinkti fiksuotą skaičių nugalėtojų ar pavyzdžių, neatskleisdami viso pertvarkyto sąrašo.
Ar galiu tai naudoti tikram prizų traukimui ar loterijai?
Taip, neoficialioms dovanų akcijoms ir traukimams tai puikiai tinka, nes atsitiktinumas tikrai tolygus. Teisiškai reguliuojamai loterijai su piniginiais prizais patikrinkite vietinius teisės aktus — kai kuriose jurisdikcijose reikalaujamas specifinis, patikrinamas traukimo procesas.
Ar dublikatų šalinimas pakeičia mano originalų sąrašą?
Ne — dublikatų šalinimas paveikia tik sumaišytą rezultatą, ir tik kai pažymėtas atitinkamas laukelis. Jūsų įvestas sąrašas lieka lygiai toks, koks buvo, todėl galite perjungti parinktį ir maišyti iš naujo, nieko iš naujo neįvesdami.