Keverjük a kártyátKeverjük a kártyátAz algoritmusok tanítását, a számítógépek programozását nagymértékben motiválja a játékprogramok készítése. A pénzfeldobás, a kockadobás nagyon könnyen szimulálható számítógéppel. A dobás eredményének értékelésével már viszonylag egyszerű játékprogramokat készíthetünk (például kockapóker). Nehezebb a helyzet, ha kártyázni akarunk, mert a kártyacsomag keverése - amire szinte minden kártyajátékban szükség van - némi megfontolást igényel az algoritmus megírása előtt.
A keverés valójában a kártyák egy ismétlés nélküli, véletlen permutációjának kiválasztását jelenti a lehetséges permutációk közül. A keverési algoritmusok tehát lehetővé teszik n darab (vagy kevesebb) különböző véletlenszám sorozatának választását az [1; n] intervallumból. Véletlen permutációkat használnak az úgynevezett véletlenített algoritmusokban, melyek hatékonysága nem függ a bemenő adatoktól (ezért gyakran javul). A véletlen permutációknak a játékprogramokon kívül jelentős szerepük van a számítógépes szimulációban, a kriptográfiában és a különböző hibajavító kódok elméletében. Még a genetikában is találkozunk velük.
A továbbiakban néhány keverési és osztási algoritmust ismertetünk. Az algoritmusokban a kártyák helyett az [1; n] intervallumba eső természetes számok egy véletlen permutációját állítjuk elő. Az n lapból álló csomag kártyái megfeleltethetők ezen természetes számoknak. A lapokat a lap(1..n) tömbben tároljuk. Az algoritmusokat Pascal és Visual Basic Script nyelveken realizáljuk.
A Visual Basic Script programok kirajzolják a megkevert kártyákat is (lásd: A kártyalapok megjelenítése Visual Basic Scriptben). A hta fájlokat mentés után dupla kattintással futtathatjuk. A kártyalapokat tartalmazó mappát a hta fájl mappájába kell elhelyezni. A kirajzolás miatt csak 10 lapból álló kártyacsomaggal dolgozunk, de ez nem érinti az algoritmusok lényegét.
A hta és htm fájlok esetén a keverést az F5 (Frissítés) billentyű lenyomásával ismételhetjük meg.
Az algoritmusokban
a következő eljárásokat, illetve függvényeket használjuk fel.
| Feltölt(tömb,
n): feltölti a tömb elemeit az 1-től n-ig terjedő természetes számokkal. feltölt(tömb,n)
ciklus i=1-től n-ig
tömb(i)=i
ciklus vége
eljárás vége
|
Csere(a, b): felcseréli a két argumentumot. csere(a,b) temp=a a=b b=temp eljárás vége |
Beszúr(tömb, j): a tömb első elemét beszúrja a j-edik elem után. beszúr(tömb,j)
temp=tömb(1)
ciklus i=2-től j-ig
tömb(i-1)=tömb(i)
ciklus vége
tömb(j)=temp
eljárás vége
|
Vszám(i, j): az [i, j] intervallumból kiválaszt egy véletlen egész számot. Pascal: random(j-i+1)+i Visual Basic Script: int(rnd()*(j-i+1)+i) A program elején ne felejtsük el kiadni a randomize utasítást. |
A Pascal programokban a globálisan deklarált tömböt nem adtuk meg az eljárások paraméterei között.
Első
algoritmusunk leegyszerűsítve utánozza a kártyák kézzel történő keverését.
Fogjuk a legelső kártyát, és betesszük egy véletlenszerűen kiválasztott kártya
mögé. Megint fogjuk a legelső kártyát, és betesszük egy véletlenszerűen
kiválasztott kártya mögé. Ezt a folyamatot ismételjük, amíg jól megkevert
kártyacsomagot nem kapunk.
Véletlen cserés keverés feltölt(lap,n) ciklus i=1-től k-ig j=vszám(1,n) beszúr(lap,j) ciklus vége
Hány ismétlést kell végeznünk ahhoz, hogy jól megkeverjük a csomagot? A kártyacsomagot akkor tekinthetjük jól megkevertnek, ha minden lap egy véletlenszerűen kiválasztott helyre kerül. Jelöljük a legutolsó lapot U-val. Ez addig marad a helyén, amíg ki nem választjuk a ciklusban, és utána nem teszünk egy másik lapot. 1/n annak a valószínűsége, hogy a ciklusban az utolsó lapot választjuk ki, így átlagosan n lépés után kerül az U lap mögé még egy lap. Ekkor már két hely van mögötte, tehát 2/n valószínűséggel, azaz átlagosan n/2 lépésben jut a következő lap mögéje stb. Végül az U lap jut a csomag tetejére, tehát egyetlen lépés kell még megtenni, hogy szintén véletlenszerű helyre kerüljön. Így a lépések átlagos száma összesen:
k = n + n/2 + n/3 + n/4 + ... + n/(n-1) + 1 = n(1 + 1/2 + 1/3 + ... + 1/(n-1) + 1/n)
A k értéke 32 lap esetén 130, az 52 lapos csomagnál pedig 236. A harmonikus sor összege csak lassan nő, de az eljárás a beszúrással járó sok léptetés miatt rossz hatékonyságú.
Forráskód: Pascal, Visual Basic Script (hta), Visual Basic Script (htm)
A rendezési algoritmusok ötletet nyújthatnak hatékonyabb keverések
végrehajtásához. A sok véletlen csere helyett válasszunk minden kártyalapnak egy
véletlen sorszámot, és a sorszámnak megfelelő helyre tegyük a tömbben! Sajnos az
egymástól különböző véletlenszámok sorozatának (permutációjának) kiválasztása az [1; n] intervallumból
egyenértékű magának a keverésnek a
végrehajtásával, így nem jutunk előbbre. Bizonyítható azonban, hogy ha n elemet
választunk véletlenszerűen az [1; n3] intervallumból, akkor
1-1/n valószínűséggel már különböző értékeket kapunk.
A fentiek alapján az algoritmusban a tömbelemekhez választunk egy prioritás-értéket az [1; n3] intervallumból, és a prioritásnak megfelelően rendezzük a tömböt.
Rendezéses keverés feltölt(lap,n) ciklus i=1-től n-ig prioritás(i)=vszám(1,n3) ciklus vége a lap tömb rendezése a prioritások szerint
A keverés hatékonysága a rendezés hatékonyságától függ. A mozgatások számának csökkentése miatt a minimumkiválasztásos rendezést alkalmaztuk. A módszer hátránya, hogy a prioritások tárolása újabb tömböt igényel.
Forráskód: Pascal, Visual Basic Script (hta), Visual Basic Script (htm)
A rendezéses keverés
hatékonyságát rontja, hogy a prioritások meghatározása után a két tömböt még
rendezni kell. Használjuk fel magát a rendezést a keverésre úgy, hogy az
elemeknek a "rendezés" során véletlenszerűen választunk helyet! A beillesztéses
rendezésnél például kihagyjuk az algoritmusból az i-edik elem helyének
keresését. Helyette 1 és i között véletlenszerűen kiválasztunk egy
helyet, és oda tesszük be az elemet. Előtte a rendezéshez hasonlóan a többi
elemet eggyel odébb léptetjük
Fordított rendezéses keverés
feltölt(lap,n)
ciklus i=2-től n-ig
temp=lap(i)
hely=vszám(1,i)
ciklus j=i-1-től hely-ig visszafelé
lap(j+1)=lap(j)
ciklus vége
lap(hely)=temp
ciklus vége
Sajnos a két egymásba ágyazott ciklus miatt ez az algoritmus a rendezéseknél megszokott n2-tel arányos lépésszámot igényel.
Forráskód: Pascal, Visual Basic Script (hta), Visual Basic Script (htm)
 4 szín permutációs fája |
 Véletlen permutáció kiválasztása (ha nem látszik az animáció, frissíteni kell a weblapot) |
A keverés gyorsaságának növeléséhez rajzoljuk fel az úgynevezett permutációs fát! Négy szín esetén például jelképezzük a kiválasztott színt a fa élének színével. Felülről lefelé haladva először 4 szín közül választhatunk, aztán csak 3-ból stb. Minden egyes út a gyökértől a levelekig megfelel a 4 szín egy permutációjának. Egy véletlen permutáció kiválasztása azt jelenti, hogy minden egyes elágazásnál véletlenszerűen döntjük el, merre induljunk tovább.
A keverési algoritmusban nem kell létrehoznunk a teljes fát. Elegendő mindig csak a következő lépést kiválasztani.
Kunth-keverés feltölt(lap,n) ciklus i=1-től n-ig j=vszám(i,n) csere(lap(i),lap(j)) ciklus vége
Az algoritmust A számítógép-programozás művészete című, nagy sikerű könyv szerzőjéről, Donald Knuthról nevezték el. Mint látjuk, a lépések száma n-nel arányos!
Vegyük észre, hogy az utolsó ismétlésénél valójában nem történik változás, így elegendő n-1-ig futtatni a ciklust:
ciklus i=1-től n-1-ig j=vszám(i,n) csere(lap(i),lap(j)) ciklus vége
Forráskód: Pascal, Visual Basic Script (hta), Visual Basic Script (htm)
A keverési algoritmusokat egymás után többször is végrehajthatjuk. Így az első végrehajtás után kapott véletlen permutációból újabb véletlen permutációt képezhetünk. Az ismétlésnél természetesen nincs szükség a feltölt eljárás meghívására.
Egy keverési algoritmust, azaz
a permutációk kiválasztását véletlenszerűnek
tekinthetünk, ha
Mivel n elem esetén az ismétlés nélküli permutációk száma n!, a kívánt valószínűség 1/n!. Bizonyítható, hogy a Knuth-keverés esetén ez a feltétel teljesül.
Vigyáznunk kell azonban a részletekre. Ha például a Knuth-keverésnél az [i, n] intervallum helyett az [i+1, n] intervallumból választanánk ki a kártya új helyét (azaz a lap biztosan elmozdulna a helyéről), akkor például a legelső elem egyetlen előállított permutációban sem maradna a helyén. Nem kapnánk meg tehát bármely permutációt.
Ha a Knuth-keverésnél az [i, n] intervallum helyett az [1, n] intervallumból választanánk (ahogy természetesnek gondolnánk), akkor a lehetőségek száma nn lenne az n! helyett. Így egyes permutációk választásának a valószínűsége biztosan nem lehet 1/n!, hiszen az nn általában nem osztható n!-ral. (Például 33 = 27, de 3! = 6.)
Problémát jelenthet maga a véletlenszám-generátor. Ha nem biztosítja az egyenletes eloszlást, akkor nem lesz azonos az egyes permutációk valószínűsége. Lényeges továbbá, hogy a lehetséges véletlenszámok száma elérje a permutációk számát. Mivel log2 52! = 225,58, egy 52 lapos kártyacsomag esetén legalább 226 bites véletlenszám-generátorra van szükség!
A játékokban a kártyák keverését osztás követi. Ha csak a kiosztott lapokra van szükségünk (a csomagban maradókra nem), akkor fölösleges az egész csomagot megkeverni. A keverés helyett elegendő véletlenszerűen kiválasztani a kívánt számú lapot. Ez az elemek (lapok) egy ismétlés nélküli, véletlen variációjának az előállítását igényli.
Megtehetjük ugyan, hogy egy új lap véletlenszerű választását addig-addig ismételgetjük, amíg különbözni fog az eddig kiválasztott összes laptól, de ez sok lap esetén sok fölösleges ismétléssel jár. A Knuth-féle keverési algoritmus módosítását sokkal hatékonyabban felhasználhatjuk a véletlen variáció előállítására. Egyszerűen a ciklust csak a kívánt számú (k darab) elem kiválasztásáig futtatjuk:
Knuth-osztás ciklus i=1-től k-ig j=vszám(i,n) csere(lap(i),lap(j)) ciklus vége
Forráskód: Pascal, Visual Basic Script (hta), Visual Basic Script (htm)
Algoritmusunkat akkor is használhatjuk, ha a kiválasztás sorrendje nem számít (ismétlés nélküli kombináció), hiszen az ugyanazon elemekből álló sorozatok ugyanannyiszor fordulnak elő a variációk között (k!), tehát a valószínűségük megegyezik egymással.
Ha az n jóval nagyobb mint a k, akkor az osztás fenti algoritmusa nem hatékony, hiszen végrehajtásához n elemű tömbre van szükségünk, melyet fel is kell töltenünk kezdőértékekkel. A memóriaigényt ilyenkor hasítótáblázattal csökkenthetjük. A cseréket a teljes tömb tárolása helyett elegendő kulcs-érték párokkal nyilvántartani.
Az
1 2 3 4 7 6 5 8 9
permutáció tárolása helyett például az
(5, 7)
(7, 5)
kulcs-érték párokat tároljuk. Az (5, 7) kulcs-érték pár azt jelenti, hogy az 5. helyen a 7-es szám áll.
Az i-edik tömbelem lekérdezéséhez végignézzük a hasítótábla kulcsértékeit. Ha nem szerepel bennük az i, akkor a tömbelem értéke i lesz, ha szerepel, akkor pedig a kulcsnak megfelelő érték. A fenti esetben például tömb(8)=8, de tömb(7)=5.
Ezek után az osztás (a k-ad rendű ismétlés nélküli véletlen variáció kiválasztásának) algoritmusa pontosan megegyezik a Knuth-algoritmuson alapuló osztáséval, csak az elemek cseréjét a hasítótábla segítségével kell végrehajtani:
Hasítótáblás osztás hasítótábla inicializálása ciklus i=1-től k-ig j=vszám(i,n) h-csere(i,j) ciklus vége
A csere előtt meg kell vizsgálni, hogy az i, illetve a j szerepel-e kulcsként a hasítótáblában. Ha nem, akkor fel kell venni. Ezek után tudjuk végrehajtani a cserét:
h-csere(i,j) ha i nem szerepel kulcsként akkor az (i,i) pár felvétele a hasítótáblába elágazás vége ha j nem szerepel kulcsként akkor a (j,j) pár felvétele a hasítótáblába elágazás vége az (i,x) és a (j,y) párok értékének cseréje (i,y), (j,x)-re
Az algoritmus lefutása után a véletlen variáció elemeit a kulcsok kiolvasásával kapjuk meg a hasítótáblából.
Forráskód: Pascal, Visual Basic Script (hta), Visual Basic Script (htm)
A Knuth-féle osztási algoritmussal ellentétben ezen algoritmus ismételt alkalmazása előtt újra inicializálni kell a hasítótáblát.
Az algoritmust felhasználhatjuk például lottószámok választására, és minden egyéb, ismétlés nélküli véletlen variáció vagy kombináció előállítására.
Visual Basic Scriptben nagyon könnyen és látványosan megjeleníthetjük a kártyalapokat. Kép elhelyezéséhez az <IMG> elemet kell beírni a weblap forráskódjába (image: kép). Az elem src tulajdonságában megadjuk a képfájl elérési útját (source: forrás). Mivel idézőjelen belül nem nyithatunk újabb idézőjelet, helyette aposztrófot használunk:
document.write "<img src='elérési út'> "
A kép bárhol lehet az elérhető háttértárakon vagy az Interneten. Megadhatunk relatív és abszolút elérési utat is.
Helyezzük el a kártyalapokat kirajzoló képfájlokat a program mappájának lapok nevű almappájába. Egyszerűen tudunk hivatkozni rájuk, ha a lap sorszámát választjuk fájlnévnek: 1.gif, 2.gif, 3.gif stb. Az elérési utat az almappa nevéből, a fájlnevet jelölő indexből és a kiterjesztésből állíthatjuk össze:
"<img src='lapok\" & lap(i) & ".gif'> "
Ha a lap(i) értéke például 5, akkor a document.write utasítás a következő sztringet írja a weblap forráskódjába:
<img src='lapok\5.gif'>
A hta fájlok futtatása előtt töltsük le a kártyalapokat, és kicsomagolva helyezzük el a mappát a hta fájlokkal megegyező mappába.
A kártyalapok letöltése
Összeállította: Juhász Tibor
A képek forrása:
Card shuffling tutorial
Magic for All
TechUser.Net
Wikipedia