Javascript 生成加权随机数

Generate A Weighted Random Number

提问by Todd Sharp

I'm trying to devise a (good) way to choose a random number from a range of possible numbers where each number in the range is given a weight. To put it simply: given the range of numbers (0,1,2) choose a number where 0 has an 80% probability of being selected, 1 has a 10% chance and 2 has a 10% chance.

我正在尝试设计一种（好的）方法来从一系列可能的数字中选择一个随机数，其中该范围内的每个数字都被赋予一个权重。简单地说：给定数字范围 (0,1,2)，选择一个数字，其中 0 有 80% 的概率被选中，1 有 10% 的几率被选中，2 有 10% 的几率被选中。

It's been about 8 years since my college stats class, so you can imagine the proper formula for this escapes me at the moment.

我的大学统计课已经过去了大约 8 年，所以你可以想象此刻我无法找到正确的公式。

Here's the 'cheap and dirty' method that I came up with. This solution uses ColdFusion. Yours may use whatever language you'd like. I'm a programmer, I think I can handle porting it. Ultimately my solution needs to be in Groovy - I wrote this one in ColdFusion because it's easy to quickly write/test in CF.

这是我想出的“又便宜又脏”的方法。此解决方案使用 ColdFusion。您可以使用任何您喜欢的语言。我是一名程序员，我想我可以处理移植它。最终我的解决方案需要在 Groovy 中 - 我在 ColdFusion 中编写了这个，因为它很容易在 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 ) );    
}

I'm looking for better solutions, please suggest improvements or alternatives.

我正在寻找更好的解决方案，请提出改进​​或替代方案。

回答by maerics

Rejection sampling(such as in your solution) is the first thing that comes to mind, whereby you build a lookup table with elements populated by their weight distribution, then pick a random location in the table and return it. As an implementation choice, I would make a higher order function which takes a spec and returns a function which returns values based on the distribution in the spec, this way you avoid having to build the table for each call. The downsides are that the algorithmic performance of building the table is linear by the number of items and there could potentially be a lot of memory usage for large specs (or those with members with very small or precise weights, e.g. {0:0.99999, 1:0.00001}). The upside is that picking a value has constant time, which might be desirable if performance is critical. In JavaScript:

拒绝抽样（例如在您的解决方案中）是第一个想到的事情，即您构建一个查找表，其中包含按权重分布填充的元素，然后在表中随机选择一个位置并返回它。作为一种实现选择，我会创建一个高阶函数，它接受一个规范并返回一个函数，该函数根据规范中的分布返回值，这样您就不必为每次调用构建表。缺点是构建表的算法性能与项目数量呈线性关系，并且对于大型规范（或那些具有非常小或精确权重的成员，例如 {0:0.99999, 1 :0.00001})。好处是选择一个值有恒定的时间，如果性能至关重要，这可能是可取的。在 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.
    // E.g. the spec {0:0.999, 1:0.001} will break this impl.
    for (j=0; j<spec[i]*10; j++) {
      table.push(i);
    }
  }
  return function() {
    return table[Math.floor(Math.random() * table.length)];
  }
}
var rand012 = weightedRand({0:0.8, 1:0.1, 2:0.1});
rand012(); // random in distribution...

Another strategy is to pick a random number in [0,1)and iterate over the weight specification summing the weights, if the random number is less than the sum then return the associated value. Of course, this assumes that the weights sum to one. This solution has no up-front costs but has average algorithmic performance linear by the number of entries in the spec. For example, in JavaScript:

另一种策略是选择一个随机数[0,1)并在权重规范上迭代求和，如果随机数小于总和，则返回相关值。当然，这假设权重总和为 1。该解决方案没有前期成本，但平均算法性能与规范中的条目数量呈线性关系。例如，在 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...

回答by Thomas Eding

Generate a random number R between 0 and 1.

生成一个介于 0 和 1 之间的随机数 R。

If R in [0, 0.1) -> 1

如果 R 在 [0, 0.1) -> 1

If R in [0.1, 0.2) -> 2

如果 R 在 [0.1, 0.2) -> 2

If R in [0.2, 1] -> 3

如果 R 在 [0.2, 1] -> 3

If you can't directly get a number between 0 and 1, generate a number in a range that will produce as much precision as you want. For example, if you have the weights for

如果您不能直接获得 0 到 1 之间的数字，请生成一个范围内的数字，该数字将产生所需的精度。例如，如果你有权重

(1, 83.7%) and (2, 16.3%), roll a number from 1 to 1000. 1-837 is a 1. 838-1000 is 2.

(1, 83.7%) 和 (2, 16.3%) 掷出一个从 1 到 1000 的数字。1-837 是 1。838-1000 是 2。

回答by qw3n

Here are 3 solutions in javascript since I'm not sure which language you want it in. Depending on your needs one of the first two might work, but the the third one is probably the easiest to implement with large sets of numbers.

这里有 3 种 javascript 解决方案，因为我不确定您想要哪种语言。根据您的需要，前两种中的一种可能有效，但第三种可能最容易用大量数字实现。

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<weight.length;i++){
    //amt+=weight[i]; *alternative method
    //if(n<amt){
    if(n<weight[i]){
      return num[i];
    }
  }
}

weight=[80,90,100];
//weight=[80,10,10]; *alternative method
num=[0,1,2]

回答by Greg Case

This is more or less a generic-ized version of what @trinithis wrote, in Java: I did it with ints rather than floats to avoid messy rounding errors.

这或多或少是@trinithis 在 Java 中编写的内容的通用版本：我使用整数而不是浮点数来完成它以避免混乱的舍入错误。

static class Weighting {

    int value;
    int weighting;

    public Weighting(int v, int w) {
        this.value = v;
        this.weighting = w;
    }

}

public static int weightedRandom(List<Weighting> 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<Weighting> weightings = new ArrayList<Weighting>();
    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));
    }
}

回答by Tom Roggero

I use the following

我使用以下

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

This is my go-to "weighted" random, where I use an inverse function of "x" (where x is a random between min and max) to generate a weighted result, where the minimum is the most heavy element, and the maximum the lightest (least chances of getting the result)

这是我的首选“加权”随机数，我使用“x”的反函数（其中 x 是最小值和最大值之间的随机数）来生成加权结果，其中最小值是最重的元素，最大值是最轻（获得结果的机会最小）

So basically, using weightedRandom(1, 5)means the chances of getting a 1 are higher than a 2 which are higher than a 3, which are higher than a 4, which are higher than a 5.

所以基本上，使用weightedRandom(1, 5)意味着获得 1 的机会高于 2，高于 3，高于 4，高于 5。

Might not be useful for your use case but probably useful for people googling this same question.

可能对您的用例没有用，但可能对谷歌搜索同样问题的人有用。

After a 100 iterations try, it gave me:

经过 100 次迭代尝试，它给了我：

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

回答by emory

How about

怎么样

int [ ] numbers = { 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 2 } ;

int [] numbers = { 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 2 } ;

then you can randomly select from numbers and 0 will have an 80% chance, 1 10%, and 2 10%

然后您可以从数字中随机选择，0 将有 80% 的机会，1 10% 和 2 10%

回答by Raimi bin Karim

8 years late but here's my solution in 3 lines.

晚了 8 年，但这是我的 3 行解决方案。

1) Prepare an array of probability mass functionsuch that

1) 准备一个概率质量函数数组，使得

pmf[array_index] = P(X=array_index):

pmf[array_index] = P(X=array_index):

var pmf = [0.8, 0.1, 0.1]

2) Prepare an array for the corresponding cumulative distribution functionsuch that

2) 为对应的累积分布函数准备一个数组，使得

cdf[array_index] = F(X=array_index):

cdf[array_index] = F(X=array_index):

var cdf = pmf.map((sum => value => sum += value)(0))
// [0.8, 0.9, 1]

3a) Generate a random number.

3a) 生成一个随机数。

3b) Get an array of elements which are more than or equal to this number.

3b) 获取大于或等于该数字的元素数组。

3c) Return its length.

3c) 返回其长度。

cdf.filter(el => Math.random() >= el).length

回答by Garmekain

This one is in Mathematica, but it's easy to copy to another language, I use it in my games and it can handle decimal weights:

这个在 Mathematica 中，但很容易复制到另一种语言，我在我的游戏中使用它，它可以处理十进制权重：

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]]
    ]
]

(Now I'm talking with a lists first element's index equals 0)The idea behind this is that having a normalized list weightsthere is a chance of weights[n]to return the index n, so the distances between the min and max at step nshould be weights[n]. The total distance from the minimum min (which we put it to be 0)and the maximum max is the sum of the list weights.

（现在我正在谈论列表第一个元素的索引等于 0）这背后的想法是，拥有标准化列表权重有机会weights[n]返回索引n，因此 min 和 max 之间的距离在步骤n应该是weights[n]。与最小最小值（我们将其设为 0）和最大值最大值的总距离是列表权重的总和。

The good thing behind this is that you don't append to any array or nest for loops, and that increases heavily the execution time.

这背后的好处是您不会附加到任何数组或嵌套 for 循环，这会大大增加执行时间。

Here is the code in C# without needing to normalize the weightslist and deleting some code:

这是 C# 中的代码，无需标准化权重列表并删除一些代码：

int WeightedRandom(List<float> 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;
}

回答by j2emanue

here is the input and ratios : 0 (80%), 1(10%) , 2 (10%)

这是输入和比率：0 (80%), 1(10%), 2 (10%)

lets draw them out so its easy to visualize.

让我们把它们画出来，这样很容易形象化。

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

lets add up the total weight and call it TR for total ratio. so in this case 100. lets randomly get a number from (0-TR) or (0 to 100 in this case) . 100 being your weights total. Call it RN for random number.

让我们将总重量相加，并将其称为总比值 TR。所以在这种情况下 100. 让我们从 (0-TR) 或 (0 到 100 在这种情况下) 随机获取一个数字。100 是您的总重量。将其称为随机数 RN。

so now we have TR as the total weight and RN as the random number between 0 and TR.

所以现在我们将 TR 作为总权重，RN 作为 0 和 TR 之间的随机数。

so lets imagine we picked a random # from 0 to 100. Say 21. so thats actually 21%.

所以让我们想象一下，我们从 0 到 100 中随机选择了一个#。比如说 21。所以实际上是 21%。

WE MUST CONVERT/MATCH THIS TO OUR INPUT NUMBERS BUT HOW ?

我们必须将其转换/匹配到我们的输入数字，但如何转换？

lets loop over each weight (80, 10, 10) and keep the sum of the weights we already visit. the moment the sum of the weights we are looping over is greater then the random number RN (21 in this case), we stop the loop & return that element position.

让我们循环遍历每个权重 (80, 10, 10) 并保留我们已经访问过的权重之和。当我们循环的权重总和大于随机数 RN（在本例中为 21）时，我们停止循环并返回该元素位置。

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

lets say the random number (between 0 and 100) is 83. Lets do it again:

假设随机数（0 到 100 之间）是 83。让我们再做一次：

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

回答by Nina Scholz

I suggest to use a continuous check of the probability and the rest of the random number.

我建议使用对概率和其余随机数的连续检查。

This function sets first the return value to the last possible index and iterates until the rest of the random value is smaller than the actual probability.

此函数首先将返回值设置为最后一个可能的索引并迭代，直到剩余的随机值小于实际概率。

The probabilities have to sum to one.

概率之和必须为 1。

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