Algoritmi - Estrazione viziata da probabilità

Forum - Algoritmi - Estrazione viziata da probabilità

pistilloi (Normal User)
Newbie

Messaggi: 9
Iscritto: 03/12/2010

Postato alle 16:44
Domenica, 28/07/2013

Buona sera, avrei bisogno di un'algoritmo che dati: un'insieme di elementi e la probabilità che ogni elemento ha d'esser estratto; generi con maggio frequenza gli elementi più probabili.

Un'input d'esempio può essere:

A = {a,b,c,d,e,f}

a=0.5
b=0.05
c=0.1
d=0.02
e=0.3
f=0.03

Il numero di elementi da estrarre è minore della cardinalità di A, per esempio 4 elementi.

arack95 (Member)
Pro

Messaggi: 144
Iscritto: 15/11/2010

Postato alle 16:21
Lunedì, 29/07/2013

Non mi sembra troppo difficile come problema, tu come hai provato a risolverlo? Posta qualche idea così ne discutiamo

pistilloi (Normal User)
Newbie

Messaggi: 9
Iscritto: 03/12/2010

Postato alle 21:10
Lunedì, 29/07/2013

Ho cambiato totalmente approccio, mettendo tutte le parole del mio dizionari in un file(urna) privo di spazzi, a quel punto l'algoritmo estrae semplicemente numeri casuali da 1 a "numero totale di caratteri" e pesca il carattere in quella posizione.

Non è come l'idea iniziale ma funziona, che ti pare?

arack95 (Member)
Pro

Messaggi: 144
Iscritto: 15/11/2010

Postato alle 11:49
Martedì, 30/07/2013

Cioè crei una stringa da 100 caratteri e inserisci 3 volte 'f', 30 volte 'e' e così via e poi trovi un numero random tra 1 e 100 ed estrai così l'elemento?

Io avevo pensato ad un'altra soluzione, generi un numero a virgola mobile compreso tra 0 e 1 e poi usare un algoritmo del tipo:

Codice sorgente - presumibilmente Delphi

value rand = [0 .. 1]
value sum = 0
 
foreach element in array
        sum = sum + element.value
        if ( rand <= sum )
                return element
        end { if }
end { foreach }

Però se hai molti elemementi potrebbe essere lento ripetere quel foreach, quindi potrebbe essere ottimizzato generando prima un insieme di numeri random e poi facendo il check di tutti quanti i numeri nell'if.
Sicuramente esisterà una soluzione migliore :-|

Edit.
element.value sarebbe la probabilità che l'elemento venga estratto, nel caso di 'a' ad esempio 0.5.

Spiegami meglio la tua soluzione, sono curioso

Ultima modifica effettuata da arack95 il 30/07/2013 alle 11:52