obter item aleatório ponderado

51

Eu tenho, por exemplo, esta tabela

+ ----------------- +
| frutas | peso
+ ----------------- +
| maçã 4
| laranja 2
| limão | 1 |
+ ----------------- +

Eu preciso devolver uma fruta aleatória. Mas a maçã deve ser colhida 4 vezes mais que o limão e 2 vezes mais que a laranja .

Em um caso mais geral, deve ser f(weight)muitas vezes frequente.

O que é um bom algoritmo geral para implementar esse comportamento?

Ou talvez haja algumas jóias prontas em Ruby? :)

PS:
Eu implementei o algoritmo atual no Ruby https://github.com/fl00r/pickup

fl00r
fonte
11
que deve ser a mesma para a obtenção de fórmula saque aleatória em Diablo :-)
Jalayn
11
@Jalayn: Na verdade, a idéia para a solução de intervalo na minha resposta abaixo vem do que eu lembro sobre tabelas de combate no World of Warcraft. :-D
Benjamin Kloster
Veja também
BlueRaja - Danny Pflughoeft 26/09
Eu implementei vários algoritmos aleatórios ponderados simples . Deixe-me saber se você tem perguntas.
usar o seguinte código

Respostas:

50

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

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 apropriado). Obviamente, isso não é muito eficiente em termos de memória e requer pesos inteiros.


Outra abordagem um pouco mais complicada seria assim:

  1. Calcule as somas acumuladas de pesos:

    intervals = [4, 6, 7]

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

  2. Gere um número aleatório nno intervalo de 0até sum(weights).

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

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

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

Benjamin Kloster
fonte
2
a solução intervalo parece bom
Jalayn
11
Esse foi meu primeiro pensamento :). Mas e se eu tiver uma mesa com 100 frutas e peso, pode ficar em torno de 10k? Será uma matriz muito grande e isso não será tão eficiente quanto eu quero. É sobre a primeira solução. A segunda solução parece boa
fl00r
11
Eu implementei esse algoritmo no Ruby github.com/fl00r/pickup
fl00r
11
O método alias é a maneira mais fácil de lidar com isso . Sinceramente, fico surpreso com o número de postagens que repetem o mesmo código várias vezes, ignorando o método alias . pelo amor de Deus, você obtém desempenho em tempo constante!
Opa
30

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

Isso se baseia no seguinte raciocínio: vamos selecionar o primeiro elemento da nossa sequência como "resultado atual"; em cada iteração, mantenha-o ou descarte-o e escolha o novo elemento como atual. Podemos calcular a probabilidade de qualquer elemento ser selecionado no final como um produto de todas as probabilidades de que ele não seria descartado nas etapas subsequentes, vezes a probabilidade de que ele fosse 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 itera apenas a sequência de entrada uma vez, ele funciona mesmo com sequências obscenamente grandes, desde que a soma de pesos se encaixe em um int(ou você pode escolher algum tipo maior para esse contador)

deixa pra lá
fonte
2
Eu avaliaria isso antes de assumir que é melhor apenas porque itera uma vez. Gerar tantos valores aleatórios também não é exatamente rápido.
Jean-Bernard Pellerin
11
@ Jean-Bernard Pellerin eu fiz, e é realmente mais rápido em grandes listas. A menos que você use um gerador aleatório criptograficamente forte (-8
Nevermind,
Deve ser a resposta aceita imo. Eu gosto disso melhor do que a abordagem "intervalo" e "entrada repetida".
Vivin Paliath
2
Eu só queria dizer que voltei a esse tópico 3 ou 4 vezes nos últimos dois anos para usar esse método. Esse método conseguiu repetidamente fornecer as respostas necessárias com rapidez suficiente para meus propósitos. Eu gostaria de poder aprovar esta resposta toda vez que voltei a usá-la.
Jim Yarbro
11
Ótima solução se você realmente tiver que escolher apenas uma vez. Caso contrário, a preparação da solução na primeira resposta uma vez é muito mais eficiente.
Deduplicator
22

As respostas já presentes são boas e eu as expandirei um pouco.

Como Benjamin sugeriu, somas cumulativas são normalmente usadas neste 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 pedaço de código do Nevermind. Este pedaço de código C # que eu costumo usar:

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. Qual é a eficiência dessa abordagem e qual é a solução mais eficiente? Meu pedaço de código requer O (n) de memória e é executado em O (n) tempo. Eu não acho que isso possa 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 for 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. Na pior das hipóteses, a atualização do peso para um elemento causa a atualização de somas cumulativas para todos os elementos, aumentando a complexidade da atualização para O (n) . Isso também pode ser reduzido para O (log n) usando a árvore indexada binária .

Imperador Orionii
fonte
Bom ponto sobre pesquisa binária
fl00r
A resposta de Nevermind não precisa de espaço extra; portanto, é O (1), mas aumenta a complexidade do tempo de execução gerando números aleatórios e avaliando a função de peso repetidamente (que, dependendo do problema subjacente, pode ser cara).
Benjamin Kloster
11
O que você afirma ser "versão mais legível" do meu código não é realmente. Seu código precisa saber a soma total de pesos e somas cumulativas com antecedência; o meu não.
Nevermind
@Benjamin Kloster Meu código chama a função de peso apenas uma vez por elemento - você não pode fazer nada melhor do que isso. Você está certo sobre números aleatórios, no entanto.
Nevermind
@Nevermind: você chama apenas uma vez por chamada para a função de seleção, portanto, se o usuário chama duas vezes, a função de peso é chamada novamente para cada elemento. É claro que você pode armazená-lo em cache, mas não é mais O (1) para complexidade de espaço.
Benjamin Kloster
8

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

Nos algoritmos genéticos, esse procedimento de seleção é chamado seleção proporcional de aptidão ou seleção de roda de roleta, pois:

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

Seleção de roleta

Os algoritmos típicos têm complexidade O (N) ou O (log N), mas você também pode executar O (1) (por exemplo , seleção de roleta através de aceitação estocástica ).

manlio
fonte
Você sabe qual é a fonte original desta imagem? Quero usá-lo para um artigo, mas preciso ter certeza da atribuição.
Malcolm MacLeod
@MalcolmMacLeod Desculpe, é usado em muitos artigos / sites do GA, mas não sei quem é o autor.
Manlio 18/05
0

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 (% 98) retornará 0, que é o índice de 'apple' para a matriz especificada.

Além disso, esse 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);

Dá uma saída algo assim:

Start...
Head count:52
Tails count:48
Ramazan POLAT
fonte
2
Programadores trata de questões conceituais e espera-se que as respostas expliquem as coisas. Jogar dumps de código em vez de explicação é como copiar código do IDE para o quadro branco: pode parecer familiar e até às vezes compreensível, mas parece estranho ... apenas estranho. Whiteboard não tem compilador
mosquito
Você está certo, eu estava focado no código, então esqueci de dizer como ele funciona. Vou adicionar uma explicação sobre como isso funciona.
Ramazan Polat