Hogyan tudnám megoldani hogy egy tömb eleme randomban generálás esetén nem lehet ugyanaz mint egy másik indexen lévő elem?

Az algoritmus:

1. Generálsz egy véletlenszerű elemet és eltárolod egy változóban.

2. Ha a tömb első (nulladik) elemét generáltad, akkor eltárolod a tömbben.

3. Ha a második (első) vagy nagyobbik elemét generáltad, akkor leellenőrzöd, hogy az előző elem megegyezik az újonnan generálttal. Ha egyezik, vissza az 1. lépésre; ha nem egyezik akkor eltárolod a tömb elemeként.

"hogy az előző elem megegyezik az újonnan generálttal"

Bocs, elírtam - helyesen: "előző elemek megegyeznek-e"

Csúnyán. :(

Beágyazol egy ciklust a ciklusba, amivel a generálást végzed, ez végigmegy a tömb addigi elemein összehasonlítja az aktuálissal, és ha talál megegyezőt, akkor az indexet nem növeled, hanem ugyanarra az elemre kérsz egy újabb random számot a következő iterációban (ha a generálásban vizsgálod, nulla-e eredetileg, akkor a beágyazott ciklusban beállítasz egy flaget, hogy abben az esetben ne vizsgálja, ha van megegyező).

Talán az okosok tudnak mondani szebb megoldást is, mert ez csúnya és még lassú is.

Szebb megoldás: rekurzió, mert az újragenerált cucc valami mással lehet egyenlő. Vagyis kell egy eljárás, amit a ciklusban meghívsz, és addig hívja az eljárás önmagát, amíg a tömb aktuális eleme egy másikkal sem egyezik meg. Vagyis: a generálást végző ciklusban hívsz egy eljárást, ami kb ugyanazt csinálja, mint a fenti beágyazott cucc, csak a végén meghívod önmagát újra. Ha minden pöpec, akkor kilép az eljárásból, visszatér a ciklusba és megy tovább.

Ez is csúnya és lassú, de egy fokkal átláthatóbb.

A legegyszerűbb az, amit az első mondott, csak ez attól függően, hogy a generálandó számok menynisége hogyan aránylik az intervallum méretéhez amiből generálsz, igen hosszúra elnyúlhat. Az általam preferált metodika a következő:

Nem írtál nyelvet, de feltételezem hogy van benne valamilyen map adatszerkezet (Dictionary, Map, stb). Ennek a szerkezetnek a lényege, hogy a sima tömbhöz képest nem csak az értékeket magukat tárolod el, hanem az egyes értékekhez hozzárendelhetsz egy kulcsot is, amin keresztül eléred majd őket. Ez a kulcs lehet szám, string, akármi.

A folyamat lényege: Tegyük fel, hogy 1 és N közötti számokat akarsz generálni, K darabot.

Indítasz egy for ciklust, (i=0; i<K; i++). Első körben kigenerálod az első számot, és a kigenerált számot indexként ahsználva eltárolod a Map-ben az 1-et. (myMap[random_number] = 1). A következő lépésben már 2 és N között generálsz egy számot, és az előzőhöz hasonlóan, a generált szám indexén eltárolod a 2-t. Általánosságban véve, ha 1-től kezdve generálnál számokat, akkor minden lépésben 1+i és N között generálsz számot, és az 1+i értéket tárolod el a kigenerált szám kulcsán. Kivéve, amikor olyan számot generálsz ki, aminek a kulcsa már létezik. Ebben az esetben a kulcson levő értéket előveszed, és saját magával felveszed, az eredeti értéket meg felülírod az új sorszámmal. (Például az 5-ödik lépésben van egy 48=>2 kulcs=>érték párod, és kisorsolod megint a 48-at. Ekkor eltárolod a 2=>2 kulcs=>érték párt, és a 48=>2-t átírod 48=>5-re.)

Ennek a metodikának a szépsége, hogy garantáltan ismétlés nélkül generálhatsz vele számokat, a futásideje lényegében O(K) (magyarul a futásidő egyenesen arányos K-val, vagyis a kisorsolandó számok mennyiségével), és az árnyalatnyival egyszerűbb változatához képest memóriakímélőbb is. Picit komplikáltabb, de optimálisabb.

#6 Egy optimalizációs lépést kivéve átalakítható úgy, hogy a sorrend megörződik, egyszerűen amikor azonos számot sorsolsz, akkor nem az eredeti kulcson ütöd felül az értéket, és veszed fel a korábbi sorszámot önmagával, hanem a régi sorszámon veszed fel az új sorszámot. (tehát az előző példában szereplő 48:5 és 2:2 helyett marad a 48:2 és 2:5 lesz). Ennek a hátránya, hogy láncolódik, tehát minél többször sorsolod ki ugyanazt a számot, annál több elemen kell végigmásznod, mire eljutsz a legfrissebbhez. Viszont a tárolt értékek megörzik az eredeti sorszámokat.

Az, hogy a sorsolt számok nem egészek... nos, itt az a kérdés, hogy pontosan miről van szó. Ha van egy diszkrét, predefiniált lista, amiben történetesen nemegész számok vannak, akkor a számokat, amiket sorsolsz mindenképp letárolod. Ezesetben a map-es móka lecserélhető egy egyszerűbb metodikára, ahol egyszerűen a sorsolt számot kicseréled a lista első, második, i. elemével. Ez a metodika azért hátrányosabb, mert el kell tárolni a teljes számhalmazt, amiből generálsz, de ha ez adott, akkor nincs akadálya.

Ha viszont arról van szó, hogy full random 0 és N között akármilyen float/double kijöhet eredményül, akkor úgy hiszem nincs értelme trükközni, egy ekkora számhalmazon rettentő pici esélye van az ismétlődésnek, még többezer szám sorsolásakor is.