Solutie Problema

In primul rand imi cer scuze pentru intarziere cu care scriu acest post (am fost prins cu diferite chestii nesemnificative cum ar fi sesiunea - care nu merge f bine btw).

Problema era asa:
Dandu-se o lista simplu inlatuita de lungime necunoscuta sa se gaseasca un algoritm care returneaza un element random din aceasta lista printr-o singura parcurgere. Problema se rezolva in felul urmator.

La pasul 1 alegem elementul de pe pozitia 1.
La pasul i alegem elementul de pe pozitia i cu o probabilitate de 1 / i.

Voi scrie algoritmul intr-un pseudocod pentru a fi mai clar.

ret = 0
pointer = baza listei
for (i = 1; pointer != null; i++, p = p->next) {
if (rand(i) == 0) {
ret = p->valoare;
}
}

Practic la fiecare pas inlocuiesc elementul returnat cu elementul aflat pe pozitia aceea cu o probabilitate de 1 / i, iar la sfarsit returnez elementul din ret.

De ce toate elementele au aceeasi probabilitate?

Demonstratia se face cu o inductie simpla.

pasul 1.
Lista are lungime 1, elementul returnat este chiar primul din lista -> evident.

pasul i.
Sa zicem ca am ajuns la elementul i si am ales deja un element din primele i-1 elemente cu probabilitatea 1 / (i - 1). Acum avem probabilitate (i - 1) / i ca elementul dinainte sa ramana si 1 / i ca acesta sa fie inlocuit.
Avand in vedere ca elementul de dinainte avea deja probabilitatea 1 / (i - 1) probabilitatea ca acesta sa fie continuare e (1 / (i - 1)) * ((i - 1) / i) = 1 / i.
Evident probabilitatea elementul ales sa fie cel din casuta i e 1 / i deci elementul ales va avea probabilitatea 1 / i.

Daca aveti nelamuriri puteti sa imi trimite-ti si sper sa va raspund cat de curand cu lamuriri :).

Problema a fost rezolvata de:
- Cosmin Gheorge
- Andrei Dragus
- Tudor Muresan & Cristi Urlea (au lucrat la comun)
- Dan Sanduleac

Am mai auzit o idee care mie nu mi se pare ok insa o sa postez aici argumentele mele impotriva ei.
La fiecare pas generam un numar random si la sfarsit alegem elementul cu cheia minima. In practica aceasta idee merge insa ce te faci in cazuri de egalitate? Cineva a zis ca in cazul in care ai egalitate intre 2 elemente dai cu banu pe care sa il iei (adica fifty - fifty chance) insa nu vad cum ai putea argumenta corectitudinea acestei solutii. Din aceasta cauza am respins aceasta solutie (oricum toti cei care au venit cu solutia asta au revenit ulterior cu solutia buna). Nestiind insa lungimea listei nu prea stii in ce interval sa generezi acele numere riscand astfel sa ai multe egalitati ceea ce ar duce la dubiosenii :D. Daca reuseste cineva sa demonstreze ca merge sa dai cu banul in caz de egalitate il invit sa posteze aici comment sau sa imi trimita un mail.