Come scegliere un oggetto in base alla sua probabilità?

Question

Ho una lista di articoli. Ognuno di questi elementi ha una sua probabilità.

Qualcuno può suggerire un algoritmo per selezionare un articolo in base alla sua probabilità?

Answer 1

Quindi, con ogni elemento memorizzare un numero che segna la sua relativa probabilità, ad esempio, se si dispone di 3 articoli si dovrebbe essere due volte più probabilità di essere selezionato come uno degli altri due allora la vostra lista avrà:

[{A,1},{B,1},{C,2}] 

Quindi sommare i numeri della lista (cioè 4 nel nostro caso). Ora generare un numero casuale e scegliere quell'indice. int index = rand.nextInt (4); restituisce il numero tale che l'indice si trova nell'intervallo corretto.

codice Java:

class Item { 
    int relativeProb; 
    String name; 

    //Getters Setters and Constructor 
} 

... 

class RandomSelector { 
    List<Item> items = new List(); 
    Random rand = new Random(); 
    int totalSum = 0; 

    RandomSelector() { 
     for(Item item : items) { 
      totalSum = totalSum + item.relativeProb; 
     } 
    } 

    public Item getRandom() { 

     int index = rand.nextInt(totalSum); 
     int sum = 0; 
     int i=0; 
     while(sum < index) { 
      sum = sum + items.get(i++).relativeProb; 
     } 
     return items.get(Math.max(0,i-1)); 
    } 
} 

Answer 2

finta che abbiamo la seguente lista

Item A 25% 
Item B 15% 
Item C 35% 
Item D 5% 
Item E 20% 

nascondiamo che tutte le probabilità sono interi, e assegnare ogni voce di un "range" che calcolato come segue.

Start - Sum of probability of all items before 
End - Start + own probability 

I nuovi numeri sono i seguenti

Item A 0 to 25 
Item B 26 to 40 
Item C 41 to 75 
Item D 76 to 80 
Item E 81 to 100 

Ora scegliere un numero casuale da 0 a 100. Diciamo che si sceglie 32. 32 cadute nella gamma Voce di B.

mj

Answer 3

si può provare il Roulette Wheel Selection.

Per prima cosa, aggiungi tutte le probabilità, quindi ridimensiona tutte le probabilità nella scala di 1, dividendo ciascuna per la somma. Supponiamo che le probabilità siano A(0.4), B(0.3), C(0.25) and D(0.05). Quindi puoi generare un numero a virgola mobile casuale nell'intervallo [0, 1]. Ora si può decidere in questo modo:

random number between 0.00 and 0.40 -> pick A 
       between 0.40 and 0.70 -> pick B 
       between 0.70 and 0.95 -> pick C 
       between 0.95 and 1.00 -> pick D 

Si può anche farlo con numeri interi casuali - dici si genera un numero intero casuale compreso tra 0 e 99 (inclusi), allora si può fare decisione come sopra.

Answer 4

1. Generare un numero casuale distribuito uniformemente.
2. Scorrere l'elenco fino a quando la probabilità cumulativa degli elementi visitati è maggiore del numero casuale

codice di esempio:

double p = Math.random(); 
double cumulativeProbability = 0.0; 
for (Item item : items) { 
    cumulativeProbability += item.probability(); 
    if (p <= cumulativeProbability) { 
     return item; 
    } 
} 

Answer 5

risposta di Brent è buona, ma non tiene conto della possibilità di erroneamente scegliere un oggetto con una probabilità pari a 0 nei casi in cui p = 0. È abbastanza facile da gestire controllando la probabilità (o forse non aggiungendo l'elemento in primo luogo):

double p = Math.random(); 
double cumulativeProbability = 0.0; 
for (Item item : items) { 
    cumulativeProbability += item.probability(); 
    if (p <= cumulativeProbability && item.probability() != 0) { 
     return item; 
    } 
} 

Answer 6

Il mio metodo è piuttosto semplice. Genera un numero casuale.Ora, poiché le probabilità dei tuoi oggetti sono note, è sufficiente scorrere l'elenco ordinato di probabilità e selezionare l'elemento la cui probabilità è minore del numero generato casualmente.

Per ulteriori dettagli, leggere la risposta here.

Answer 7

Algoritmo descritto in Ushman's, Brent's e le risposte di @ kaushaya sono implementate nella libreria Apache commons-math.

Date un'occhiata a EnumeratedDistribution classe (codice Groovy segue):

def probabilities = [ 
    new Pair<String, Double>("one", 25), 
    new Pair<String, Double>("two", 30), 
    new Pair<String, Double>("three", 45)] 
def distribution = new EnumeratedDistribution<String>(probabilities) 
println distribution.sample() // here you get one of your values 

noti che somma delle probabilità non ha bisogno di essere uguale a 1 o 100 - sarà normalizzato automaticamente.

Answer 8

Un modo lento ma semplice per farlo è quello di fare in modo che ogni membro scelga un numero casuale in base alla sua probabilità e scelga quello con il valore più alto.

Analogia:

Immagina 1 di 3 persone hanno bisogno di essere scelto, ma hanno diverse probabilità. Gli dai la morte con diverse facce. I dadi della prima persona hanno 4 facce, 2 della 2a persona e 8 della terza persona. Lanciano il loro dado e quello con il maggior numero vince.

Diciamo che abbiamo il seguente elenco:

[{A,50},{B,100},{C,200}]

Pseudocodice:

A.value = random(0 to 50); 
B.value = random(0 to 100); 
C.value = random (0 to 200); 

Prendiamo quella con il valore più alto.

Questo metodo sopra non mappa esattamente le probabilità. Ad esempio 100 non avrà il doppio di possibilità di 50. Ma possiamo farlo in un secondo modificando leggermente il metodo.

Metodo 2

Invece di scegliere un numero da 0 a peso possiamo limitare dal limite superiore della variabile precedente aggiunta della variabile corrente.

[{A,50},{B,100},{C,200}]

pseudocodice:

A.lowLimit= 0; A.topLimit=50; 
B.lowLimit= A.topLimit+1; B.topLimit= B.lowLimit+100 
C.lowLimit= B.topLimit+1; C.topLimit= C.lowLimit+200 

risultante limiti

A.limits = 0,50 
B.limits = 51,151 
C.limits = 152,352 

Poi scegliere un numero casuali da 0 a 352 e confrontarlo con limiti di ciascuna variabile di vedere se il numero casuale è nei suoi limiti.

Credo che questo tweak abbia prestazioni migliori poiché esiste solo una generazione casuale.

C'è un metodo simile in altre risposte, ma questo metodo non richiede che il totale sia 100 o 1.00.

Answer 9

È possibile utilizzare il codice di Julia:

function selrnd(a::Vector{Int}) 
    c = a[:] 
    sumc = c[1] 
    for i=2:length(c) 
     sumc += c[i] 
     c[i] += c[i-1] 
    end 
    r = rand()*sumc 
    for i=1:length(c) 
     if r <= c[i] 
      return i 
     end 
    end 
end 

Questa funzione restituisce l'indice di un elemento in modo efficiente.