Véletlenszerű Lista Keverő - Ingyenes Online Lista Véletlenszerűsítő Eszköz

Mi az a véletlenszerű listakeverő?

A véletlenszerű listakeverő olyan eszköz, amely fogadja a listaelemeket, majd új, véletlenszerű sorrendbe rendezi őket. Írjon be neveket, feladatokat vagy bármi mást, soronként egyet, az eszköz pedig úgy rendezi át őket, hogy minden lehetséges sorrend azonos eséllyel jelenjen meg. Az eszköz a Fisher–Yates-keverést használja, amely jól ismert algoritmus torzítatlan véletlenszerű sorrendek előállítására.

A véletlenszerű listakeverő használata

1. Írja be vagy illessze be a listát a mezőbe, soronként egy elemet.
2. Kattintson a „Lista véletlenszerűsítése” gombra. Az elemek azonnal átrendeződnek.
3. Olvassa el a gomb alatt megjelenő, új sorrend szerint számozott kevert listát.
4. Kattintson ismét a „Lista véletlenszerűsítése” gombra egy új, az előzőtől független keveréshez.
5. Kattintson az „Eredmény másolása” gombra az új sorrend másolásához, vagy a „Törlés” gombra az újrakezdéshez.

A bemenet üres sorait a rendszer automatikusan eltávolítja, így a további sortörések nem hoznak létre üres bejegyzéseket az eredmények között.

Hogyan működik a Fisher–Yates-keverési algoritmus?

A Fisher–Yates-keverés egyszer végighalad a listán: az utolsó elemtől indul, és a lista eleje felé halad. Minden lépésben véletlenszerűen kiválaszt egy elemet a lista még el nem helyezett részéből, majd felcseréli azt az aktuális pozícióban lévő elemmel.

A Fisher–Yates-keverés képlete

Egy n elemű, a 0 pozíciótól az n − 1 pozícióig számozott lista esetén:

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

A ciklus n − 1 alkalommal fut le, így a keverés összesen körülbelül n lépést igényel. Ezt lineáris időnek nevezzük, jelölése O(n). Mivel az algoritmus minden pozíciót pontosan egyszer vesz figyelembe, és minden alkalommal egy fokozatosan szűkülő, pontosan meghatározott elemhalmazból választ, az n! (n faktoriális: n × (n − 1) × ... × 1) lehetséges sorrend mindegyikének azonos az esélye, hogy eredményként jelenjen meg.

Példa: egy négy elemű lista keverése

Kezdjünk négy elemmel a 0–3 pozíciókban: Alma, Banán, Cseresznye, Datolya.

• i = 3: a véletlenszerű választás j = 0. A 3 és a 0 pozíciók felcserélése → Datolya, Banán, Cseresznye, Alma
• i = 2: a véletlenszerű választás j = 2. Ha egy pozíciót önmagával cserélünk fel, semmi sem változik → Datolya, Banán, Cseresznye, Alma
• i = 1: a véletlenszerű választás j = 0. A 1 és a 0 pozíciók felcserélése → Banán, Datolya, Cseresznye, Alma

Végső sorrend: Banán, Datolya, Cseresznye, Alma.

Négy elem esetén 4! = 24 lehetséges sorrend van. Mindegyiknek, így ennek is, 1/24 az esélye, hogy egy adott keverésnél jelenjen meg.

Miért nem cserélünk fel egyszerűen véletlenszerű párokat?

Egy egyszerűbbnek tűnő módszer – két véletlenszerű pozíció kiválasztása és felcserélése, ezt többször megismételve – véletlenszerűnek látszik, de valójában nem az. Az 1950-es évek néhány korai keverőprogramja így működött, és észrevétlenül bizonyos sorrendeket előnyben részesített másokkal szemben, noha egyetlen futtatás sem tűnt gyanúsnak. A Fisher–Yates-keverés ezt elkerüli, mert minden elem pontosan egyszer kerül áthelyezésre, egy olyan pozícióba, amelyet a lehetőségek pontosan szűkülő halmazából választ ki; ettől válik minden végső sorrend egyformán valószínűvé.

Honnan származik a Fisher–Yates-keverés?

Ronald Fisher és Frank Yates 1938-ban írták le a módszert egy statisztikai táblázatokat tartalmazó könyvben, kísérletek tervezésekor végzett kézi keveréshez. 1964-ben Richard Durstenfeld számítógépekre alakította át, így a lista helyben átrendezhetővé vált anélkül, hogy egy második listára lett volna szükség a még hátralévő elemek nyomon követéséhez. Donald Knuth ezt a számítógépes változatot is felvette 1969-es, The Art of Computer Programming című könyvébe, ezért néha Knuth-keverésnek is nevezik. A webböngészők ma is ugyanezt az algoritmust használják.

A listakeverő gyakori használati módjai

• Annak meghatározása, hogy a tanulók milyen sorrendben adnak elő vagy válaszolnak a kérdésekre az órán
• Versenyágak véletlenszerű feltöltése vagy a játékon belüli körsorrend meghatározása
• Egy csoport véletlenszerű csapatokra osztása
• Étterem, film vagy feladat kiválasztása egy rövid listáról anélkül, hogy valamelyik lehetőséget előnyben részesítenénk

Az egyszerű keverés nem mindig megfelelő. Ha bizonyos elemeknek gyakrabban kell megjelenniük, mint másoknak, a súlyozott kiválasztás jobb megoldás. Ha minden kategóriának garantáltan képviseltetnie kell magát, a rétegzett mintavétel jobban megfelel, mint egyetlen véletlenszerű keverés.

Gyakran ismételt kérdések

Valóban véletlenszerű a keverés?

Az eszköz a webböngésző pszeudovéletlenszám-generátorára (PRNG) támaszkodik, amely olyan számsorozatokat állít elő, amelyek gyakorlati szempontból véletlenszerűnek tűnnek. Ez megfelelő órai sorrendekhez, versenyek résztvevőinek véletlenszerű besorolásához vagy filmválasztáshoz. Kriptográfiai célokra, szerencsejáték-rendszerekhez vagy olyan helyzetekben nem készült, ahol a kiszámíthatatlanságtól pénz vagy biztonság függ; ezekhez tanúsított véletlenszám-generátorokra van szükség.

Elküldi az eszköz a listámat egy szerverre?

Maga a keverés teljes egészében a böngészőben, JavaScript használatával fut, ezért a lista átrendezéséhez nincs szükség hálózati kérésre. Az aktuális lista a weboldal címébe is bekerül, így újratöltéskor vagy könyvjelző használatakor sem vész el. Ha ezt a címet kimásolják, megosztják vagy újra megnyitják, a lista vele együtt továbbítódik, többek között ahhoz a szerverhez is, amely később betölti az oldalt. Ha ez szempont, ne helyezzen érzékeny információkat a listába.

Mi történik a duplikált elemekkel?

A duplikátumok megmaradnak. Ha a bemenetben a „Sam” kétszer szerepel, a kevert kimenetben is kétszer fog megjelenni, akár eltérő pozíciókban.

Van korlátozás arra, hogy hány elemet keverhetek meg?

Az eszközbe nincs beépítve korlátozás. Mivel a keverés lineáris időben fut, még a hosszú listák is a másodperc törtrésze alatt átrendeződnek bármely modern eszközön.

Miben különbözik a keverés a rendezéstől?

A rendezés rögzített szabály, például az ábécésorrend szerint rendezi az elemeket, és ugyanarra a bemenetre mindig ugyanazt az eredményt adja. A keverés véletlenszerűen rendezi az elemeket, ezért szinte minden alkalommal más sorrendet eredményez, még azonos bemenet esetén is.

Megkeverhetem ugyanazt a listát egynél többször?

Igen. A „Lista véletlenszerűsítése” gombra kattintva az algoritmus minden alkalommal újra lefut, az előző keverésektől függetlenül. Rövid lista esetén véletlenül ismétlődhet egy korábbi sorrend; hosszabb listánál ennek az esélye rendkívül csekély.