obtener un elemento aleatorio ponderado

51

Tengo, por ejemplo, esta tabla

+ ----------------- +
El | fruta | peso |
+ ----------------- +
El | manzana | 4 |
El | naranja | 2 |
El | limon | 1 |
+ ----------------- +

Necesito devolver una fruta al azar. Pero la manzana se debe recoger 4 veces más frecuente que el limón y 2 veces más frecuente que la naranja .

En el caso más general, debería ser f(weight)veces con frecuencia.

¿Cuál es un buen algoritmo general para implementar este comportamiento?

¿O tal vez hay algunas gemas listas en Ruby? :)

PD
: he implementado el algoritmo actual en Ruby https://github.com/fl00r/pickup

fl00r
fuente
11
esa debería ser la misma fórmula para obtener un botín aleatorio en Diablo :-)
Jalayn
1
@Jalayn: En realidad, la idea de la solución de intervalo en mi respuesta a continuación proviene de lo que recuerdo sobre las tablas de combate en World of Warcraft. :-D
Benjamin Kloster
Ver también
BlueRaja - Danny Pflughoeft
He implementado varios algoritmos aleatorios ponderados simples . Déjeme saber si usted tiene preguntas.
Leonid Ganeline

Respuestas:

50

La solución conceptualmente más simple sería crear una lista donde cada elemento ocurra tantas veces como su peso, por lo que

fruits = [apple, apple, apple, apple, orange, orange, lemon]

Luego, use las funciones que tenga a su disposición para elegir un elemento aleatorio de esa lista (por ejemplo, generar un índice aleatorio dentro del rango adecuado). Por supuesto, esto no es muy eficiente con la memoria y requiere pesos enteros.


Otro enfoque un poco más complicado se vería así:

  1. Calcule las sumas acumuladas de pesos:

    intervals = [4, 6, 7]

    Cuando un índice inferior a 4 representa una manzana , 4 a inferior a 6 una naranja y 6 a inferior a 7 un limón .

  2. Genere un número aleatorio nen el rango de 0a sum(weights).

  3. Encuentra el último artículo cuya suma acumulativa está arriba n. El fruto correspondiente es tu resultado.

Este enfoque requiere un código más complicado que el primero, pero menos memoria y cómputo, y admite pesos de punto flotante.

Para cualquiera de los algoritmos, el paso de configuración se puede hacer una vez para un número arbitrario de selecciones aleatorias.

Benjamin Kloster
fuente
2
la solución de intervalo parece agradable
Jalayn
1
Este fue mi primer pensamiento :). Pero, ¿qué pasa si tengo una mesa con 100 frutas y el peso podría ser de alrededor de 10k? Será una matriz muy grande y esto no será tan eficiente como quiero. Esto se trata de la primera solución. La segunda solución se ve bien
fl00r
1
He implementado este algoritmo en Ruby github.com/fl00r/pickup
fl00r
1
El método alias es la forma de facto de manejar esto . Sinceramente, estoy asombrado por la cantidad de publicaciones que repiten el mismo código una y otra vez, todo mientras se ignora el método alias . ¡por el amor de Dios, obtienes un rendimiento de tiempo constante!
opa
30

Aquí hay un algoritmo (en C #) que puede seleccionar un elemento aleatorio ponderado de cualquier secuencia, solo iterando a través de él una vez:

public static T Random<T>(this IEnumerable<T> enumerable, Func<T, int> weightFunc)
{
    int totalWeight = 0; // this stores sum of weights of all elements before current
    T selected = default(T); // currently selected element
    foreach (var data in enumerable)
    {
        int weight = weightFunc(data); // weight of current element
        int r = Random.Next(totalWeight + weight); // random value
        if (r >= totalWeight) // probability of this is weight/(totalWeight+weight)
            selected = data; // it is the probability of discarding last selected element and selecting current one instead
        totalWeight += weight; // increase weight sum
    }

    return selected; // when iterations end, selected is some element of sequence. 
}

Esto se basa en el siguiente razonamiento: seleccionemos el primer elemento de nuestra secuencia como "resultado actual"; luego, en cada iteración, guárdelo o descarte y elija un nuevo elemento como actual. Podemos calcular la probabilidad de que cualquier elemento dado sea seleccionado al final como un producto de todas las probabilidades de que no se descarte en los pasos posteriores, multiplicado por la probabilidad de que se seleccione en primer lugar. Si hace los cálculos, verá que este producto se simplifica a (peso del elemento) / (suma de todos los pesos), ¡que es exactamente lo que necesitamos!

Dado que este método solo itera sobre la secuencia de entrada una vez, funciona incluso con secuencias obscenamente grandes, siempre que la suma de pesos se ajuste a un int(o puede elegir un tipo más grande para este contador)

No importa
fuente
2
Yo compararía esto antes de asumir que es mejor solo porque itera una vez. Generar tantos valores aleatorios tampoco es exactamente rápido.
Jean-Bernard Pellerin
1
@ Jean-Bernard Pellerin lo hice, y en realidad es más rápido en listas grandes. A menos que use un generador aleatorio criptográficamente fuerte (-8
importa
Debería ser la respuesta aceptada imo. Esto me gusta más que el enfoque de "intervalo" y "entrada repetida".
Vivin Paliath
2
Solo quería decir que he vuelto a este hilo 3 o 4 veces en los últimos dos años para usar este método. Este método ha tenido éxito repetidamente en proporcionar las respuestas que necesito lo suficientemente rápido para mis propósitos. Ojalá pudiera votar esta respuesta cada vez que volviera a usarla.
Jim Yarbro
1
Buena solución si realmente solo tienes que elegir una vez. De lo contrario, hacer el trabajo de preparación para la solución en la primera respuesta una vez es mucho más eficiente.
Deduplicador
22

Las respuestas ya presentes son buenas y las ampliaré un poco.

Como Benjamin sugirió, las sumas acumulativas se usan típicamente en este tipo de problema:

+------------------------+
| fruit  | weight | csum |
+------------------------+
| apple  |   4    |   4  |
| orange |   2    |   6  |
| lemon  |   1    |   7  |
+------------------------+

Para encontrar un elemento en esta estructura, puede usar algo como el código de Nevermind. Este fragmento de código C # que suelo usar:

double r = Random.Next() * totalSum;
for(int i = 0; i < fruit.Count; i++)
{
    if (csum[i] > r)
        return fruit[i];
}

Ahora a la parte interesante. ¿Qué tan eficiente es este enfoque y cuál es la solución más eficiente? Mi código requiere memoria O (n) y se ejecuta en tiempo O (n) . No creo que se pueda hacer con menos de O (n) espacio, pero la complejidad del tiempo puede ser mucho menor, de hecho O (log n) . El truco consiste en utilizar la búsqueda binaria en lugar del ciclo regular for.

double r = Random.Next() * totalSum;
int lowGuess = 0;
int highGuess = fruit.Count - 1;

while (highGuess >= lowGuess)
{
    int guess = (lowGuess + highGuess) / 2;
    if ( csum[guess] < r)
        lowGuess = guess + 1;
    else if ( csum[guess] - weight[guess] > r)
        highGuess = guess - 1;
    else
        return fruit[guess];
}

También hay una historia sobre la actualización de pesos. En el peor de los casos, la actualización de peso para un elemento provoca la actualización de sumas acumulativas para todos los elementos, lo que aumenta la complejidad de la actualización a O (n) . Eso también se puede reducir a O (log n) usando un árbol indexado binario .

Emperador Orionii
fuente
Buen punto sobre la búsqueda binaria
fl00r
La respuesta de Nevermind no necesita espacio adicional, por lo que es O (1), pero agrega complejidad de tiempo de ejecución al generar repetidamente números aleatorios y evaluar la función de peso (que, dependiendo del problema subyacente, podría ser costoso).
Benjamin Kloster
1
Lo que usted dice ser "versión más legible" de mi código en realidad no lo es. Su código necesita conocer de antemano la suma total de pesos y sumas acumulativas; el mío no.
importa
@Benjamin Kloster Mi código solo llama a la función de peso una vez por elemento; no puede hacer nada mejor que eso. Sin embargo, tienes razón sobre los números aleatorios.
importa
@Nevermind: solo lo llama una vez por llamada a la función de selección, por lo que si el usuario lo llama dos veces, la función de peso se llama nuevamente para cada elemento. Por supuesto, puede almacenarlo en caché, pero ya no es O (1) por la complejidad del espacio.
Benjamin Kloster
8

Esta es una implementación simple de Python:

from random import random

def select(container, weights):
    total_weight = float(sum(weights))
    rel_weight = [w / total_weight for w in weights]

    # Probability for each element
    probs = [sum(rel_weight[:i + 1]) for i in range(len(rel_weight))]

    slot = random()
    for (i, element) in enumerate(container):
        if slot <= probs[i]:
            break

    return element

y

population = ['apple','orange','lemon']
weights = [4, 2, 1]

print select(population, weights)

En algoritmos genéticos, este procedimiento de selección se denomina Selección proporcional de aptitud física o Selección de rueda de ruleta, ya que:

  • Se asigna una proporción de la rueda a cada una de las posibles selecciones en función de su valor de peso. Esto se puede lograr dividiendo el peso de una selección por el peso total de todas las selecciones, normalizándolas a 1.
  • entonces se realiza una selección aleatoria similar a cómo se gira la ruleta.

Selección de rueda de ruleta

Los algoritmos típicos tienen complejidad O (N) u O (log N), pero también puede hacer O (1) (por ejemplo , selección de rueda de ruleta mediante aceptación estocástica ).

manlio
fuente
¿Sabes cuál es la fuente original de esta imagen? Quiero usarlo para un trabajo pero necesito asegurarme de la atribución.
Malcolm MacLeod
@MalcolmMacLeod Lo sentimos, se usa en muchos documentos / sitios de GA, pero no sé quién es el autor.
manlio
0

Esta esencia está haciendo exactamente lo que estás pidiendo.

public static Random random = new Random(DateTime.Now.Millisecond);
public int chooseWithChance(params int[] args)
    {
        /*
         * This method takes number of chances and randomly chooses
         * one of them considering their chance to be choosen.    
         * e.g. 
         *   chooseWithChance(0,99) will most probably (%99) return 1
         *   chooseWithChance(99,1) will most probably (%99) return 0
         *   chooseWithChance(0,100) will always return 1.
         *   chooseWithChance(100,0) will always return 0.
         *   chooseWithChance(67,0) will always return 0.
         */
        int argCount = args.Length;
        int sumOfChances = 0;

        for (int i = 0; i < argCount; i++) {
            sumOfChances += args[i];
        }

        double randomDouble = random.NextDouble() * sumOfChances;

        while (sumOfChances > randomDouble)
        {
            sumOfChances -= args[argCount -1];
            argCount--;
        }

        return argCount-1;
    }

puedes usarlo así:

string[] fruits = new string[] { "apple", "orange", "lemon" };
int choosenOne = chooseWithChance(98,1,1);
Console.WriteLine(fruits[choosenOne]);

El código anterior probablemente devolverá (% 98) 0, que es el índice de 'manzana' para la matriz dada.

Además, este código prueba el método proporcionado anteriormente:

Console.WriteLine("Start...");
int flipCount = 100;
int headCount = 0;
int tailsCount = 0;

for (int i=0; i< flipCount; i++) {
    if (chooseWithChance(50,50) == 0)
        headCount++;
    else
        tailsCount++;
}

Console.WriteLine("Head count:"+ headCount);
Console.WriteLine("Tails count:"+ tailsCount);

Da una salida algo así:

Start...
Head count:52
Tails count:48
Ramazan POLAT
fuente
2
Los programadores se trata preguntas conceptuales y se espera que las respuestas expliquen las cosas. Lanzar volcados de código en lugar de una explicación es como copiar código del IDE a la pizarra: puede parecer familiar e incluso a veces comprensible, pero se siente extraño ... simplemente extraño. Whiteboard no tiene compilador
mosquito
Tienes razón, estaba centrado en el código, así que olvidé decir cómo funciona. Agregaré una explicación sobre cómo funciona.
Ramazan Polat