obter item aleatório ponderado

A solução conceitualmente mais simples seria criar uma lista em que cada elemento ocorre tantas vezes quanto seu peso, então

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

Em seguida, use as funções que você tem à sua disposição para escolher um elemento aleatório dessa lista (por exemplo, gerar um índice aleatório dentro do intervalo adequado). Obviamente, isso não é muito eficiente em termos de memória e requer pesos inteiros.

Outra abordagem um pouco mais complicada ficaria assim:

1. Calcule as somas cumulativas de pesos:

   intervals = [4, 6, 7]
   

   Onde um índice abaixo de 4 representa uma maçã , 4 abaixo de 6 e laranja e 6 a abaixo de 7 a limão .

2. Gere um número aleatório n no intervalo de 0 a sum(weights) .

3. Encontre o último item cuja soma acumulativa está acima de n . A fruta correspondente é o seu resultado.

Esta abordagem requer um código mais complicado do que o primeiro, mas menos memória e computação e suporta pesos de ponto flutuante.

Para qualquer algoritmo, a etapa de configuração pode ser feita uma vez para um número arbitrário de seleções aleatórias.

Aqui está um algoritmo (em C #) que pode selecionar um elemento ponderado aleatório de qualquer sequência, apenas iterando por ele uma 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. 
}

Isto é baseado no seguinte raciocínio: vamos selecionar o primeiro elemento da nossa sequência como "resultado atual"; em seguida, em cada iteração, mantenha-o ou descarte e escolha novo elemento como atual. Podemos calcular a probabilidade de qualquer dado elemento ser selecionado no final como um produto de todas as probabilidades de que ele não seria descartado em etapas subseqüentes, vezes a probabilidade de que ele seria selecionado em primeiro lugar . Se você fizer as contas, verá que este produto simplifica para (peso do elemento) / (soma de todos os pesos), que é exatamente o que precisamos!

Como esse método só repete a sequência de entrada uma vez, ele funciona até mesmo com sequências obscenamente grandes, contanto que a soma dos pesos caiba em int (ou você pode escolher um tipo maior para esse contador)

As respostas já presentes são boas e vou expandi-las um pouco.

Como Benjamin sugeriu, as somas cumulativas são normalmente usadas nesse tipo de problema:

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

Para encontrar um item nessa estrutura, você pode usar algo como o código de Nevermind. Esta parte do código C # que eu uso normalmente:

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

Agora, para a parte interessante. Quão eficiente é essa abordagem e qual é a solução mais eficiente? Meu trecho de código requer a memória O (n) e é executado em tempo O (n) . Eu não acho que isso pode ser feito com menos de O (n) espaço, mas a complexidade do tempo pode ser muito menor, O (log n) na verdade. O truque é usar a pesquisa binária em vez do loop 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];
}

Há também uma história sobre a atualização de pesos. No pior dos casos, atualizar o peso de um elemento faz com que a atualização de somas acumulativas para todos os elementos aumente a complexidade da atualização para O (n) . Isso também pode ser reduzido a O (log n) usando árvore indexada binária .

Esta é uma implementação simples em 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

e

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

print select(population, weights)

Em algoritmos genéticos, esse procedimento é chamado de Seleção proporcional de fitness ou Seleção da Roleta desde:

• uma proporção da roda é atribuída a cada uma das seleções possíveis com base em seu valor de peso. Isso pode ser obtido dividindo o peso de uma seleção pelo peso total de todas as seleções, normalizando-as para 1.
• , em seguida, é feita uma seleção aleatória semelhante à rotação da roleta.

OsalgoritmostípicostêmcomplexidadeO(N)ouO(logN),masvocêtambémpodefazerO(1)(porexemplo, Roleta- seleção de rodas via aceitação estocástica ).

Esta essência está fazendo exatamente o que você está pedindo.

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;
    }

você pode usá-lo assim:

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

O código acima provavelmente irá (% 98) retornar 0, que é o índice para 'apple' para o array dado.

Além disso, este código testa o método fornecido acima:

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);

Ele gera uma saída assim:

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