Sampling da multiset in spazio limitato

Programmazione, algoritmica, teoria dell'informazione, ...
Rispondi
Avatar utente
rand
Messaggi: 109
Iscritto il: 29 ott 2006, 01:11
Località: Vedi avatar

Sampling da multiset in spazio limitato

Messaggio da rand »

La signorina A va in giro per il suo paese alla ricerca di un fidanzato ed incontra una serie di m pretendenti che rappresentiamo con una sequenza $ s = s_1 s_2 \ldots s_m $, dove $ s_i $ è il codice fiscale dell'i-esimo tizio. Attenzione perchè nella sua visita può incontrare più volte la stessa persona, quindi $ s $ può contenere ripetizioni.

Nonostante ciò A vuole scegliere il suo boyfriend in maniera equiprobaile nell'insieme dei pretendenti distinti che ha incontrato (l'amore è cieco in questo caso). Purtroppo è davvero smemorata, può ricordarsi al massimo di $ O(\log m) $ bits, in compenso ha un potente generatore di interi pseudocasuali che associa ad ogni codice fiscale un intero tra 1 ed $ m^3 $ preso uniformemente a caso. Sotto tali vincoli A riesce nel suo intento con probabilità $ \geq 1 - 1/m $, molto elevata in pratica, quale algoritmo può usare?
Avatar utente
rand
Messaggi: 109
Iscritto il: 29 ott 2006, 01:11
Località: Vedi avatar

Messaggio da rand »

Basta generare l'intero corrispondente al codice fiscale di ogni persona incontrata e tenersi il più piccolo tra questi. Non ci voleva mica tanto a dirlo :).
Rispondi