Nejaušu sarakstu sajaucējs - Bezmaksas tiešsaistes sarakstu nejaušināšanas rīks

Kas ir nejaušs saraksta jaukšanas rīks?

Nejaušs saraksta jaukšanas rīks pieņem vienumu sarakstu un sakārto to jaunā, nejaušā secībā. Ierakstiet vārdus, uzdevumus vai jebko citu, katru vienumu jaunā rindā, un rīks tos pārkārtos tā, lai katrai iespējamajai secībai būtu vienāda iespēja tikt izvēlētai. Šis rīks izmanto Fišera–Jeitsa jaukšanu — plaši pazīstamu algoritmu neizkropļotu nejaušu secību veidošanai.

Kā izmantot nejaušas saraksta jaukšanas rīku

1. Ierakstiet vai ielīmējiet sarakstu lodziņā, katru vienumu jaunā rindā.
2. Noklikšķiniet uz “Nejaušināt sarakstu”. Vienumi tiek nekavējoties pārkārtoti.
3. Izlasiet zem pogas redzamo sajaukto sarakstu, kas numurēts jaunajā secībā.
4. Lai veiktu jaunu, no iepriekšējās neatkarīgu jaukšanu, vēlreiz noklikšķiniet uz “Nejaušināt sarakstu”.
5. Noklikšķiniet uz “Kopēt rezultātu”, lai nokopētu jauno secību, vai uz “Notīrīt”, lai sāktu no jauna.

Tukšās rindas ievadē tiek automātiski noņemtas, tāpēc papildu rindu pārtraukumi rezultātos neveidos tukšus ierakstus.

Kā darbojas Fišera–Jeitsa jaukšanas algoritms?

Fišera–Jeitsa jaukšana iziet cauri sarakstam vienu reizi, sākot ar pēdējo vienumu un virzoties uz sākumu. Katrā solī tā nejauši izvēlas vienu vienumu no tās saraksta daļas, kas vēl nav novietota, un samaina to ar pašreizējā pozīcijā esošo vienumu.

Fišera–Jeitsa jaukšanas formula

Sarakstam ar n vienumiem, kas numurēti no pozīcijas 0 līdz pozīcijai 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

Cikls tiek izpildīts n − 1 reizes, tāpēc jaukšana kopumā aizņem aptuveni n soļus. To sauc par lineāru laiku un apzīmē ar O(n). Tā kā algoritms katru pozīciju izskata tieši vienu reizi un izvēli izdara no arvien mazāka, precīzi definēta vienumu kopuma, katrai no n! iespējamajām secībām (n faktoriāls: n × (n − 1) × ... × 1) ir vienāda iespēja kļūt par rezultātu.

Piemērs: četru vienumu saraksta jaukšana

Sākumā četri vienumi atrodas pozīcijās no 0 līdz 3: Ābols, Banāns, Ķirsis, Datel̄e.

• i = 3: nejauši izvēlētais j = 0. Samaina pozīcijas 3 un 0 → Datel̄e, Banāns, Ķirsis, Ābols
• i = 2: nejauši izvēlētais j = 2. Pozīcijas samainīšana pašai ar sevi neko nemaina → Datel̄e, Banāns, Ķirsis, Ābols
• i = 1: nejauši izvēlētais j = 0. Samaina pozīcijas 1 un 0 → Banāns, Datel̄e, Ķirsis, Ābols

Galīgā secība: Banāns, Datel̄e, Ķirsis, Ābols.

Četriem vienumiem ir 4! = 24 iespējamās secības. Katrai no tām, arī šai, jebkurā jaukšanas reizē ir 1 iespēja no 24 tikt izvēlētai.

Kāpēc gan vienkārši nesamainīt nejaušus pārus?

Vienkāršāka metode — izvēlēties divas nejaušas pozīcijas un samainīt tās, atkārtojot šo darbību vairākas reizes, — izskatās nejauša, taču tāda nav. Dažas agrīnās jaukšanas programmas 1950. gados darbojās šādi un nemanāmi deva priekšroku noteiktām secībām, lai gan neviena atsevišķa izpildes reize neizskatījās aizdomīga. Fišera–Jeitsa jaukšana no tā izvairās, jo katrs vienums tiek pārvietots tieši vienu reizi uz pozīciju, kas izvēlēta no precīzi sarūkoša iespēju kopuma; tieši tāpēc katra galīgā secība ir vienlīdz ticama.

No kurienes radusies Fišera–Jeitsa jaukšana?

Statistiķi Ronalds Fišers un Frenks Jeitss šo metodi aprakstīja 1938. gadā statistikas tabulu grāmatā, lai eksperimentu izstrādes laikā sarakstus varētu jaukt ar rokām. 1964. gadā Ričards Dērstenfelds to pielāgoja datoriem, lai sarakstu varētu pārkārtot uz vietas, neizmantojot otru sarakstu atlikušo vienumu uzskaitei. Donalds Knuts šo datora versiju iekļāva savā 1969. gada grāmatā The Art of Computer Programming, tāpēc to dažkārt sauc par Knuta jaukšanu. Tīmekļa pārlūkprogrammas šo pašu algoritmu izmanto arī mūsdienās.

Biežākie saraksta jaukšanas rīka lietojumi

• Noteikt secību, kādā skolēni klasē uzstājas vai atbild uz jautājumiem
• Nejauši izveidot turnīra tabulu vai noteikt gājienu secību spēlē
• Sadalīt grupu nejaušās komandās
• Izvēlēties restorānu, filmu vai uzdevumu no īsā saraksta, nedodot priekšroku nevienai izvēlei

Vienkārša jaukšana ne vienmēr ir piemērotākā metode. Ja dažiem vienumiem jāparādās biežāk nekā citiem, labāk izmantot svērto izvēli. Ja jānodrošina visu kategoriju pārstāvniecība, stratificētā izlase ir piemērotāka nekā viena nejauša jaukšana.

Biežāk uzdotie jautājumi

Vai jaukšana patiešām ir nejauša?

Tā balstās uz tīmekļa pārlūkprogrammas pseidogadījuma skaitļu ģeneratoru (PRNG) — formulu, kas rada skaitļu virknes, kuras praktiskām vajadzībām uzvedas kā nejaušas. Ar to pietiek secību veidošanai klasē, turnīru izsēšanai vai filmas izvēlei. Tas nav paredzēts kriptogrāfijai, azartspēļu sistēmām vai jebkurai situācijai, kur nauda vai drošība ir atkarīga no neparedzamības; šādām vajadzībām nepieciešami sertificēti nejaušo skaitļu ģeneratori.

Vai rīks nosūta manu sarakstu uz serveri?

Pati jaukšana pilnībā notiek pārlūkprogrammā, izmantojot JavaScript, tāpēc saraksta pārkārtošanai tīkla pieprasījums nav vajadzīgs. Pašreizējais saraksts tiek ierakstīts arī lapas tīmekļa adresē, tāpēc atkārtota ielāde vai grāmatzīme to nezaudē. Ja šī adrese tiek nokopēta, kopīgota vai atvērta no jauna, saraksts tiek nosūtīts kopā ar to, tostarp uz jebkuru serveri, kas vēlāk ielādē šo lapu. Ja tas ir būtiski, neievietojiet sarakstā sensitīvu informāciju.

Kas notiek ar dublētiem vienumiem?

Dublikāti tiek saglabāti. Ja ievadē “Sam” parādās divas reizes, tas sajauktajā izvadē joprojām parādīsies divas reizes, iespējams, citās pozīcijās.

Vai jaukšanai ir ierobežots vienumu skaits?

Rīkam nav iebūvēta ierobežojuma. Tā kā jaukšana notiek lineārā laikā, pat gari saraksti jebkurā mūsdienīgā ierīcē tiek pārkārtoti sekundes daļā.

Ar ko jaukšana atšķiras no kārtošanas?

Kārtošana sakārto vienumus pēc noteikta principa, piemēram, alfabēta secībā, un vienādai ievadei vienmēr rada vienādu rezultātu. Jaukšana sakārto vienumus nejauši un gandrīz katru reizi rada citu secību, pat ja ievade ir identiska.

Vai vienu un to pašu sarakstu var sajaukt vairāk nekā vienu reizi?

Jā. Katrs klikšķis uz “Nejaušināt sarakstu” palaiž algoritmu no jauna neatkarīgi no iepriekšējās jaukšanas. Nelielam sarakstam nejaušības dēļ var atkārtoties tā pati secība; lielākam sarakstam tas kļūst ārkārtīgi maz ticams.