obtener un elemento aleatorio ponderado

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

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

Luego, utiliza las funciones que tienes a tu 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 en 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 debajo de 6 y naranja y 6 a debajo de 7 a limón .

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

3. Encuentre el último elemento cuya suma acumulada está por encima de n . La fruta correspondiente es tu resultado.

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

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

Aquí hay un algoritmo (en C #) que puede seleccionar elementos ponderados aleatorios de cualquier secuencia, solo iterando 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, manténgalo o deséchelo y elija el nuevo elemento como actual. Podemos calcular la probabilidad de que un elemento determinado se seleccione al final como un producto de todas las probabilidades de que no se descartaría en los pasos subsiguientes, multiplicando las probabilidades de que se seleccionara 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 se repite en la secuencia de entrada una vez, funciona incluso con secuencias obscenamente grandes, siempre que la suma de ponderaciones se ajuste a un int (o puede elegir un tipo más grande para este contador)

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

Como Benjamin sugirió que las sumas acumulativas se usan normalmente en este tipo de problema:

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

Para encontrar un elemento en esta estructura, puedes usar algo como el código de Nevermind. Esta pieza 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 la memoria O (n) y se ejecuta en O (n) . No creo que se pueda hacer con menos de O (n) espacio, pero la complejidad del tiempo puede ser mucho menor, O (log n) de hecho. El truco es usar la búsqueda binaria en lugar del bucle regular.

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, el peso de la actualización para un elemento hace que la actualización de las sumas acumuladas para todos los elementos aumente la complejidad de la actualización a O (n) . Eso también se puede reducir a O (log n) utilizando árbol indexado binario .

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 los algoritmos genéticos, este procedimiento de selección se llama Selección proporcional de aptitud o Selección de la rueda de la ruleta desde:

• 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.
• luego se hace una selección aleatoria similar a cómo se gira la rueda de la ruleta.

LosalgoritmostípicostienencomplejidadO(N)uO(logN)perotambiénpuedehacerO(1)(porejemplo, Roulette- selección de ruedas mediante aceptación estocástica ).

Esta esencia está haciendo exactamente lo que está 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]);

Lo más probable es que el código anterior (% 98) devuelva 0, que es el índice de 'apple' 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 como esta:

Start...
Head count:52
Tails count:48