Általános leírás
Írj függvényt, ami szimulál egy 5-ös lottóhúzást.
A lényeg most a keverésen lesz. Úgy oldd meg a feladatot, hogy létrehozol egy 90 elemű növekvő számokból álló listát, sorbarakod, megkevered, és kiírod az első 5 elemét.
A keverés során figyelj oda arra, hogy a keverés után a lista bármely eleme a lista bármely helyén ugyanakkora valószínűséggel fordulhasson elő.
Álljon itt egy ROSSZ példa 10 szám esetére: Egy 10 elemű listán egyszer végigmegyünk minden pozíción és mindegyik pozíció esetében feldobunk egy pénzt: Fej esetén megcseréljük a szomszédjával, írás esetén békében hagyjuk az adott helyet. Ez nem jó, mert az utolsó elem nem juthat el mindenhova, csak legfeljebb eggyel balra. De más baj is van vele: Az első elem bár bárhova eljuthat, mégsem egyenlő valószínűsségel. Az első helyen 50% eséllyel marad (I), a második helyre 25% valószínűséggel kerül (FI), a harmadik helyre 12.5% valószínűséggel kerül (FFI), ..., az utolsó helyre 100/1024 % valószínűséggel kerül. Tegyük fel most, hogy ezt a pénzdobásos cserélgetést nem egyszer játszuk el, hanem 10-szer: így az utolsó elem szerencsés dobások esetén akár a lista elejére is elkeveredhet. De a valószínűségek ekkor is egyenetlenek maradnak, így ez sem felel meg a feladat kiírásának.
Szintén ROSSZ példa ez is: Dobok egy random számot, ez az első húzás. Dobok még egy random számot. Ha ugyanaz lett, mint amit már korábban dobtam, akkor újra dobok... Ennek a programnak a futási sebessége a véletlentől függ. Minden alkalommal, mikor ilyen kódot írsz, valahol a világban meghal egy informatikus.
Az egyszerű és elegáns megoldás a Fisher-Yates-Knuth-keverés. Van hozzá ezer videó is, nyilván. Ez a beszúró rendezésre emlékeztet. Első lépésben vesz egy véletlenszerű indexet 1 és 10 között. A kapott helyen lévő számot elcseréli az első helyen lévő számmal. Aztán vesz egy 2 és 10 közötti véletlenszerű indexet, és a kapott helyen lévő indexen lévő számot elcseréli a lista második helyén lévő számmal. És így tovább...
A keverés (random rendezés) olyankor fontos igazán, mikor visszatevés nélküli mintavételt próbálunk meg megvalósítani. Ezért a lottós feladat. Azaz olyan helyzetet próbálunk modellezni, amikor úgy húzunk egy kalapból, hogy a kihúzott dolgokat már nem rakjuk vissza, azaz amit egyszer kihúztunk, azt soha többet nem húzhatjuk. Ilyenkor tehát egy keverés után csak végig kell menni az elemeken: ez a végigmenetel szimulálja azt, hogy milyen sorrendben húzzuk ki az elemeket egymás után. Egy ponton ennek vége, ahogyan a kalapból is elfogynak egy idő után a dolgok...
A programod kommunikáljon a felhasználóval! Minden bemenetet "kérjen be", és minden kimenetnél írja ki, hogy mit fog kapni a felhasználó.