lista - random element arraylist java

¿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 basado en su probabilidad?

Answer 1

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

Código de muestra:

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

Answer 2

El algoritmo descrito en las Ushman''s , Brent''s y @kaushaya se implementa en la biblioteca de Apache commons-math .

Echa un vistazo a la clase EnumeratedDistribution (sigue el código groovy):

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 probabilidades no necesita ser igual a 1 o 100 - se normalizará automáticamente.

Answer 3

Entonces, con cada artículo, almacene un número que marque su probabilidad relativa; por ejemplo, si tiene 3 elementos, uno debe tener el doble de probabilidad de ser seleccionado que 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 4

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 más detalles, lee mi respuesta here .

Answer 5

Puedes probar la selección de rueda de la ruleta .

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 puedes decidir de esta manera:

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 puedes hacerlo con enteros aleatorios, digamos que generas un entero aleatorio entre 0 y 99 (inclusive), luego puedes tomar una decisión como la de arriba.

Answer 6

Puedes usar 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.

Answer 7

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

Analogía:

Imagina que 1 de 3 personas necesita ser elegida 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 mapea 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

En lugar de elegir un número de 0 al peso, podemos limitarlos desde el límite superior de la variable anterior a la suma 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 

límites resultantes

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

Luego seleccionamos un número aleatorio de 0 a 352 y lo comparamos 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 8

pretender que tenemos la siguiente lista

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

Supongamos que todas las probabilidades son números enteros, y asignamos a cada elemento un "rango" que se calcula de la siguiente manera.

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

Los nuevos números son los siguientes

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 elija un número aleatorio de 0 a 100. Digamos que elige 32. 32 caídas en el rango del Ítem B.

mj

Answer 9

Brent''s es buena, pero no da cuenta de la posibilidad de elegir erróneamente un artículo con una probabilidad de 0 en los casos en que p = 0. Eso es fácil de manejar al verificar la probabilidad (o quizás no agregar el ítem en el 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;
    }
}