Atsitiktinių sąrašų maišytuvas - Nemokamas internetinis sąrašo atsitiktinumo kūrimo įrankis

Kas yra sąrašo atsitiktinimo įrankis?

Atsitiktinis sąrašo maišytuvas yra įrankis, kuris paima elementų sąrašą ir pateikia jį nauja atsitiktine tvarka. Įveskite vardus, užduotis ar bet ką kita, po vieną elementą eilutėje, o įrankis juos pertvarkys taip, kad kiekviena galima tvarka turėtų vienodą tikimybę. Šis įrankis naudoja Fisherio–Yateso maišymą – gerai žinomą algoritmą nešališkoms atsitiktinėms tvarkoms sudaryti.

Kaip naudoti atsitiktinį sąrašo maišytuvą

1. Įveskite arba įklijuokite sąrašą į laukelį, po vieną elementą eilutėje.
2. Spustelėkite „Atsitiktinai pertvarkyti sąrašą“. Elementai iškart pertvarkomi.
3. Perskaitykite po mygtuku pateiktą išmaišytą sąrašą, sunumeruotą nauja tvarka.
4. Dar kartą spustelėkite „Atsitiktine tvarka“, kad sąrašas būtų išmaišytas naujai ir nepriklausomai.
5. Spustelėkite „Kopijuoti rezultatą“, kad nukopijuotumėte naują tvarką, arba „Išvalyti“, kad pradėtumėte iš naujo.

Tuščios įvesties eilutės automatiškai pašalinamos, todėl papildomi eilučių lūžiai rezultatų sąraše nesukurs tuščių įrašų.

Kaip veikia Fisherio–Yateso maišymo algoritmas?

Fisherio–Yateso maišymas pereina sąrašą vieną kartą, pradėdamas nuo paskutinio elemento ir judėdamas link pradžios. Kiekviename etape iš dar nepatalpintų elementų sąrašo dalies atsitiktinai parenkamas vienas elementas ir sukeičiamas su dabartinėje pozicijoje esančiu elementu.

Fisherio–Yateso maišymo formulė

Jei sąraše yra n elementų, sunumeruotų nuo pozicijos 0 iki pozicijos 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

Ciklas vykdomas n − 1 kartų, todėl iš viso maišymas trunka maždaug n žingsnių. Tai vadinama linijiniu laiku ir žymima O(n). Kadangi algoritmas kiekvieną poziciją apsvarsto tiksliai vieną kartą ir renkasi iš palaipsniui mažėjančio, aiškiai apibrėžto elementų rinkinio, kiekviena iš n! galimų tvarkų (n faktorialas: n × (n − 1) × ... × 1) turi vienodą tikimybę tapti rezultatu.

Pavyzdys: keturių elementų sąrašo maišymas

Pradėkime nuo keturių elementų pozicijose nuo 0 iki 3: Obuolys, Bananas, Vyšnia, Datulė.

• i = 3: atsitiktinai parinkta j = 0. Sukeičiamos pozicijos 3 ir 0 → Datulė, Bananas, Vyšnia, Obuolys
• i = 2: atsitiktinai parinkta j = 2. Sukeitus poziciją su pačia savimi, niekas nepasikeičia → Datulė, Bananas, Vyšnia, Obuolys
• i = 1: atsitiktinai parinkta j = 0. Sukeičiamos pozicijos 1 ir 0 → Bananas, Datulė, Vyšnia, Obuolys

Galutinė tvarka: Bananas, Datulė, Vyšnia, Obuolys.

Jei yra keturi elementai, galimos 4! = 24 tvarkos. Kiekviena iš jų, įskaitant šią, kiekvieno maišymo metu turi tikimybę 1 iš 24.

Kodėl tiesiog nesukeitus atsitiktinių porų?

Paprastesnis atrodantis metodas – atsitiktinai parinkti dvi pozicijas ir jas sukeisti, tai pakartojant kelis kartus, atrodo atsitiktinis, tačiau toks nėra. Kai kurios ankstyvosios maišymo programos iš 1950-ųjų veikė būtent taip ir nepastebimai teikė pirmenybę kai kurioms tvarkoms, nors nė vienas atskiras paleidimas neatrodė įtartinas. Fisherio–Yateso maišymas to išvengia, nes kiekvienas elementas perkeliamas tiksliai vieną kartą į poziciją, parenkamą iš tiksliai mažėjančio galimų pasirinkimų rinkinio. Dėl to kiekviena galutinė tvarka yra vienodai tikėtina.

Iš kur atsirado Fisherio–Yateso maišymas?

Statistikai Ronaldas Fisheris ir Frankas Yatesas šį metodą aprašė 1938 m. statistinių lentelių knygoje, skirtoje sąrašams maišyti rankomis planuojant eksperimentus. 1964 m. Richardas Durstenfeldas pritaikė jį kompiuteriams, kad sąrašą būtų galima pertvarkyti vietoje, nenaudojant antro sąrašo likusiems elementams sekti. Donaldas Knuthas šią kompiuterinę versiją įtraukė į savo 1969 m. knygą Kompiuterinio programavimo menas, todėl ji kartais vadinama Knutho maišymu. Tą patį algoritmą šiandien naudoja žiniatinklio naršyklės.

Dažniausi sąrašo atsitiktinimo įrankio naudojimo būdai

• Nustatyti tvarką, kuria mokiniai pristatys darbus arba atsakys į klausimus klasėje
• Sudaryti atsitiktinę turnyro lentelę arba nustatyti ėjimo tvarką žaidime
• Atsitiktinai suskirstyti grupę į komandas
• Iš trumpesnio sąrašo išrinkti restoraną, filmą ar užduotį, nesuteikiant pirmenybės kuriam nors pasirinkimui

Paprastas maišymas ne visada yra tinkamiausias. Jei kai kurie elementai turi pasirodyti dažniau nei kiti, geriau tinka atranka pagal svorius. Jei reikia garantuoti kiekvienos kategorijos atstovavimą, stratifikuotoji atranka veikia geriau nei vienas atsitiktinis maišymas.

Dažnai užduodami klausimai

Ar maišymas iš tikrųjų yra atsitiktinis?

Jis priklauso nuo žiniatinklio naršyklės pseudoatsitiktinių skaičių generatoriaus (PRNG) – formulės, kuri sudaro skaičių sekas, praktiniais tikslais elgiančias kaip atsitiktinės. To pakanka tvarkai klasėje sudaryti, turnyro dalyviams parinkti ar filmui išrinkti. Šis generatorius nėra skirtas kriptografijai, lošimų sistemoms ar bet kam, kur pinigai arba saugumas priklauso nuo nenuspėjamumo; tam reikia sertifikuotų atsitiktinių skaičių generatorių.

Ar įrankis siunčia mano sąrašą į serverį?

Pats maišymas vykdomas tik naršyklėje naudojant „JavaScript“, todėl sąrašui pertvarkyti tinklo užklausos nereikia. Dabartinis sąrašas taip pat įrašomas į puslapio žiniatinklio adresą, todėl iš naujo įkėlus puslapį arba atvėrus žymę jis neprarandamas. Jei šis adresas nukopijuojamas, bendrinamas arba atidaromas iš naujo, sąrašas keliauja kartu su juo, taip pat ir į bet kurį serverį, kuris vėliau įkelia tą puslapį. Jei tai svarbu, į sąrašą nedėkite neskelbtinos informacijos.

Kas nutinka pasikartojantiems elementams?

Pasikartojantys elementai išsaugomi. Jei įvestyje „Sam“ pasirodo du kartus, išmaišytame rezultate jis vis tiek pasirodys du kartus, galbūt skirtingose pozicijose.

Ar yra ribojamas elementų, kuriuos galiu išmaišyti, skaičius?

Įrankyje įtaisytos ribos nėra. Kadangi maišymas vykdomas per linijinį laiką, net ilgi sąrašai bet kuriame šiuolaikiniame įrenginyje pertvarkomi per sekundės dalį.

Kuo maišymas skiriasi nuo rūšiavimo?

Rikiuojant elementai išdėstomi pagal fiksuotą taisyklę, pavyzdžiui, abėcėlės tvarka, todėl tais pačiais įvesties duomenimis visada gaunamas tas pats rezultatas. Maišant elementai išdėstomi atsitiktine tvarka, todėl beveik kiekvieną kartą gaunama kitokia tvarka, net jei įvestis identiška.

Ar galiu tą patį sąrašą išmaišyti daugiau nei vieną kartą?

Taip. Kiekvienas spustelėjimas „Atsitiktine tvarka“ dar kartą paleidžia algoritmą nepriklausomai nuo ankstesnio maišymo. Jei sąrašas mažas, atsitiktinai gali pasikartoti ta pati tvarka; didesniame sąraše tai tampa itin mažai tikėtina.