Gerar um número random ponderado

Estou tentando conceber uma (boa) maneira de escolher um número random de um intervalo de números possíveis, onde cada número no intervalo recebe um peso. Simplificando: dado o intervalo de números (0,1,2), escolha um número em que 0 tem 80% de probabilidade de ser selecionado, 1 tem 10% de chance e 2 tem 10% de chance.

Já faz uns 8 anos desde a minha aula de statistics da faculdade, então você pode imaginar que a fórmula apropriada para isso me escapa no momento.

Aqui está o método “barato e sujo” que eu criei. Esta solução usa o ColdFusion. Você pode usar qualquer idioma que quiser. Eu sou um programador, acho que posso lidar com isso. Por fim, minha solução precisa estar no Groovy – escrevi este no ColdFusion porque é fácil gravar / testar rapidamente no CF.

public function weightedRandom( Struct options ) { var tempArr = []; for( var o in arguments.options ) { var weight = arguments.options[ o ] * 10; for ( var i = 1; i<= weight; i++ ) { arrayAppend( tempArr, o ); } } return tempArr[ randRange( 1, arrayLen( tempArr ) ) ]; } // test it opts = { 0=.8, 1=.1, 2=.1 }; for( x = 1; x<=10; x++ ) { writeDump( weightedRandom( opts ) ); } 

Estou procurando por melhores soluções, por favor sugira melhorias ou alternativas.

A amostragem de rejeição (como na sua solução) é a primeira coisa que vem à mente, por meio da qual você cria uma tabela de pesquisa com elementos preenchidos pela distribuição de peso, escolhe um local random na tabela e o retorna. Como uma escolha de implementação, eu faria uma function de ordem mais alta que pega uma especificação e retorna uma function que retorna valores baseados na distribuição na especificação, assim você evita ter que construir a tabela para cada chamada. As desvantagens são que o desempenho algorítmico de construir a tabela é linear pelo número de itens e pode haver muito uso de memory para especificações grandes (ou com membros com pesos muito pequenos ou precisos, por exemplo, {0: 0.99999, 1 : 0.00001}). A vantagem é que escolher um valor tem tempo constante, o que pode ser desejável se o desempenho for crítico. Em JavaScript:

 function weightedRand(spec) { var i, j, table=[]; for (i in spec) { // The constant 10 below should be computed based on the // weights in the spec for a correct and optimal table size. // Eg the spec {0:0.999, 1:0.001} will break this impl. for (j=0; j 

Outra estratégia é escolher um número random em [0,1) e iterar sobre a especificação de peso sumndo os pesos, se o número random for menor que a sum e retornar o valor associado. Claro, isso pressupõe que os pesos summ um. Esta solução não tem custos iniciais, mas tem desempenho algorítmico médio linear pelo número de inputs na especificação. Por exemplo, em JavaScript:

 function weightedRand2(spec) { var i, sum=0, r=Math.random(); for (i in spec) { sum += spec[i]; if (r <= sum) return i; } } weightedRand2({0:0.8, 1:0.1, 2:0.1}); // random in distribution... 

Gere um número random R entre 0 e 1.

Se R em [0, 0,1) -> 1

Se R em [0,1, 0,2) -> 2

Se R em [0,2, 1] -> 3

Se você não conseguir obter diretamente um número entre 0 e 1, gere um número em um intervalo que produzirá a precisão desejada. Por exemplo, se você tiver os pesos para

(1, 83,7%) e (2, 16,3%), rolar um número de 1 a 1000. 1-837 é 1. 838-1000 é 2.

Isso é mais ou menos uma versão genérica do que @trinithis escreveu, em Java: eu fiz isso com ints ao invés de floats para evitar erros de arredondamento.

 static class Weighting { int value; int weighting; public Weighting(int v, int w) { this.value = v; this.weighting = w; } } public static int weightedRandom(List weightingOptions) { //determine sum of all weightings int total = 0; for (Weighting w : weightingOptions) { total += w.weighting; } //select a random value between 0 and our total int random = new Random().nextInt(total); //loop thru our weightings until we arrive at the correct one int current = 0; for (Weighting w : weightingOptions) { current += w.weighting; if (random < current) return w.value; } //shouldn't happen. return -1; } public static void main(String[] args) { List weightings = new ArrayList(); weightings.add(new Weighting(0, 8)); weightings.add(new Weighting(1, 1)); weightings.add(new Weighting(2, 1)); for (int i = 0; i < 100; i++) { System.out.println(weightedRandom(weightings)); } } 

Aqui estão 3 soluções em javascript desde que eu não tenho certeza em qual idioma você quer. Dependendo das suas necessidades, um dos dois primeiros pode funcionar, mas o terceiro é provavelmente o mais fácil de implementar com grandes conjuntos de números.

 function randomSimple(){ return [0,0,0,0,0,0,0,0,1,2][Math.floor(Math.random()*10)]; } function randomCase(){ var n=Math.floor(Math.random()*100) switch(n){ case n<80: return 0; case n<90: return 1; case n<100: return 2; } } function randomLoop(weight,num){ var n=Math.floor(Math.random()*100),amt=0; for(var i=0;i 

E se

int [] números = {0, 0, 0, 0, 0, 0, 0, 0, 1, 2};

então você pode selecionar aleatoriamente de números e 0 terá 80% de chance, 1 10% e 2 10%

Eu uso o seguinte

 function weightedRandom(min, max) { return Math.round(max / (Math.random() * max + min)); } 

Este é o meu random “ponderado”, onde eu uso uma function inversa de “x” (onde x é um random entre min e max) para gerar um resultado ponderado, onde o mínimo é o elemento mais pesado, e o máximo o mais leve (menos chances de obter o resultado)

Então, basicamente, usando weightedRandom(1, 5) significa que as chances de obter 1 são maiores que 2 que são maiores que 3, que são maiores que 4, que são maiores que 5.

Pode não ser útil para seu caso de uso, mas provavelmente é útil para pessoas pesquisando essa mesma pergunta.

Depois de 100 iterações, ele me deu:

 ================== | Result | Times | ================== | 1 | 55 | | 2 | 28 | | 3 | 8 | | 4 | 7 | | 5 | 2 | ================== 

Este é no Mathematica, mas é fácil de copiar para outro idioma, eu o uso em meus jogos e ele pode lidar com pesos decimais:

 weights = {0.5,1,2}; // The weights weights = N@weights/Total@weights // Normalize weights so that the list's sum is always 1. min = 0; // First min value should be 0 max = weights[[1]]; // First max value should be the first element of the newly created weights list. Note that in Mathematica the first element has index of 1, not 0. random = RandomReal[]; // Generate a random float from 0 to 1; For[i = 1, i <= Length@weights, i++, If[random >= min && random < max, Print["Chosen index number: " <> ToString@i] ]; min += weights[[i]]; If[i == Length@weights, max = 1, max += weights[[i + 1]] ] ] 

(Agora eu estou falando com índice de um primeiro elemento de listas igual a 0) A idéia por trás disso é que ter uma lista normalizada pesa há uma chance de pesos [n] para retornar o índice n , então as distâncias entre min e max em a etapa n deve ser pesos [n] . A distância total do mínimo mínimo (que colocamos como 0) e o máximo máximo é a sum dos pesos da lista.

A coisa boa por trás disso é que você não anexa a nenhum array nem aninha loops, e isso aumenta muito o tempo de execução.

Aqui está o código em C # sem precisar normalizar a lista de pesos e excluir algum código:

 int WeightedRandom(List weights) { float total = 0f; foreach (float weight in weights) { total += weight; } float max = weights [0], random = Random.Range(0f, total); for (int index = 0; index < weights.Count; index++) { if (random < max) { return index; } else if (index == weights.Count - 1) { return weights.Count-1; } max += weights[index+1]; } return -1; } 

aqui está a input e as proporções: 0 (80%), 1 (10%), 2 (10%)

deixa desenhá-los para que seja fácil de visualizar.

  0 1 2 -------------------------------------________+++++++++ 

Vamos sumr o peso total e chamá-lo de TR para relação total. então, neste caso, 100. permite aleatoriamente obter um número de (0-TR) ou (0 a 100, neste caso). 100 sendo seu total de pesos. Chame-o de RN para número random.

então agora temos TR como o peso total e RN como o número random entre 0 e TR.

então vamos imaginar que escolhemos um número random de 0 a 100. Digamos 21. então, na verdade, 21%.

NÓS DEVEMOS CONVERTER / COMBINAR ISTO NOS NOSSOS NÚMEROS DE ENTRADA, MAS COMO?

Vamos fazer um loop em cada peso (80, 10, 10) e manter a sum dos pesos que já visitamos. no momento em que a sum dos pesos que estamos passando é maior que o número random RN (21 neste caso), paramos o loop e retornamos a posição desse elemento.

 double sum = 0; int position = -1; for(double weight : weight){ position ++; sum = sum + weight; if(sum > 21) //(80 > 21) so break on first pass break; } //position will be 0 so we return array[0]--> 0 

Vamos dizer que o número random (entre 0 e 100) é 83. Vamos fazer de novo:

 double sum = 0; int position = -1; for(double weight : weight){ position ++; sum = sum + weight; if(sum > 83) //(90 > 83) so break break; } //we did two passes in the loop so position is 1 so we return array[1]---> 1 

Eu sugiro usar uma verificação contínua da probabilidade e o resto do número random.

Essa function define primeiro o valor de retorno para o último índice possível e repete até que o restante do valor random seja menor que a probabilidade real.

As probabilidades têm que sumr para um.

 function getRandomIndexByProbability(probabilities) { var r = Math.random(), index = probabilities.length - 1; probabilities.some(function (probability, i) { if (r < probability) { index = i; return true; } r -= probability; }); return index; } var i, probabilities = [0.8, 0.1, 0.1], count = probabilities.map(function () { return 0; }); for (i = 0; i < 1e6; i++) { count[getRandomIndexByProbability(probabilities)]++; } console.log(count); 
 .as-console-wrapper { max-height: 100% !important; top: 0; } 

Eu tenho um slotmachine e usei o código abaixo para gerar números randoms. Em probabilitiesSlotMachine, as chaves são a saída na slotmachine e os valores representam o peso.

 const probabilitiesSlotMachine = [{0 : 1000}, {1 : 100}, {2 : 50}, {3 : 30}, {4 : 20}, {5 : 10}, {6 : 5}, {7 : 4}, {8 : 2}, {9 : 1}] var allSlotMachineResults = [] probabilitiesSlotMachine.forEach(function(obj, index){ for (var key in obj){ for (var loop = 0; loop < obj[key]; loop ++){ allSlotMachineResults.push(key) } } }); 

Agora, para gerar uma saída aleatória, eu uso este código:

 const random = allSlotMachineResults[Math.floor(Math.random() * allSlotMachineResults.length)]