¿Cómo elegir un artículo por su probabilidad?

Question

Tengo una lista de elementos. Cada uno de estos elementos tiene su propia probabilidad.

¿Alguien puede sugerir un algoritmo para elegir un artículo en función de su probabilidad?

Answer 1

Así que con cada elemento almacenar un número que marca su probabilidad relativa, por ejemplo, si tiene 3 artículos uno debe ser el doble de probabilidad de ser seleccionado como cualquiera de los otros dos, entonces su lista tendrá:

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

Luego sume los números de la lista (es decir, 4 en nuestro caso). Ahora genera un número aleatorio y elige ese índice. int index = rand.nextInt (4); devuelva el número tal que el índice esté en el rango correcto.

código 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

pretender que tenemos la siguiente lista

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

vamos a pretender que todas las probabilidades son números enteros, y asignar a cada elemento de un "rango" que calcula de la siguiente manera.

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

Los nuevos números son de la siguiente manera

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 

Ahora toma un número aleatorio entre 0 y 100. Digamos que usted escoja 32. 32 caídas en gama de artículos de B.

mj

Answer 3

Puede probar la Roulette Wheel Selection.

Primero, suma todas las probabilidades, luego escala todas las probabilidades en la escala de 1, dividiendo cada una por la suma. Supongamos que las probabilidades son A(0.4), B(0.3), C(0.25) and D(0.05). Luego puede generar un número aleatorio de coma flotante en el rango [0, 1]. Ahora se puede decidir así:

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 

También puede hacerlo con números enteros aleatorios - dice a generar un entero aleatorio entre 0 y 99 (ambos inclusive), entonces usted puede tomar una decisión como la anterior.

Answer 4

1. Genera un número aleatorio distribuido uniformemente.
2. Iterar a través de su lista hasta que la probabilidad acumulada de los elementos visitados es mayor que el número aleatorio

Código de ejemplo:

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

Answer 5

respuesta de Brent es buena, pero no tiene en cuenta la posibilidad de elegir erróneamente un ítem con una probabilidad de 0 en casos donde p = 0. Eso es fácil de manejar al verificar la probabilidad (o quizás no agregar el ítem en primer lugar):

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

Mi método es bastante simple. Genera un número aleatorio.Ahora, dado que las probabilidades de sus artículos son conocidas, simplemente repita la lista ordenada de probabilidades y elija el elemento cuya probabilidad sea menor que el número generado aleatoriamente.

Para obtener más información, lea mi respuesta here.

Answer 7

Algoritmo descrito en Ushman's, Brent's y las respuestas de @ kaushaya se implementan en la biblioteca Apache commons-math.

Tome un vistazo a la clase EnumeratedDistribution (código maravilloso sigue):

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 

Tenga en cuenta que la suma de las probabilidades no tiene por qué ser igual a 1 o 100 - que se normalizará automáticamente.

Answer 8

Una manera lenta pero simple de hacerlo es hacer que cada miembro elija un número aleatorio en función de su probabilidad y elija el que tenga el valor más alto.

Analogía:

Imagínese 1 de 3 personas tiene que ser elegido, pero tienen diferentes probabilidades. Les das muerte con diferente cantidad de caras. Los dados de la primera persona tienen 4 caras, la 2da persona 6 y la tercera persona 8. Lanzan su dado y el que tenga el mayor número gana.

digamos que tenemos la siguiente lista:

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

Pseudocódigo:

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

Escogemos el que tiene el valor más alto.

Este método anterior no correlaciona exactamente las probabilidades. Por ejemplo, 100 no tendrán el doble de posibilidades de 50. Pero podemos hacerlo modificando un poco el método.

Método 2

lugar de escoger un número del 0 al peso podemos limitarlos desde el límite superior de la variable anterior a la incorporación de la variable actual.

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

pseudocódigo:

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 

resultante límites

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

Luego elegir un número aleatorio de 0 a 352 y lo comparan con los límites de cada variable para ver si el número aleatorio está en sus límites.

Creo que este ajuste tiene un mejor rendimiento ya que solo hay 1 generación aleatoria.

Hay un método similar en otras respuestas pero este método no requiere que el total sea 100 o 1.00.

Answer 9

Usted podría utilizar el código 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 

Esta función devuelve el índice de un elemento de manera eficiente.