加权随机整数 [英] Weighted random integers

问题描述

我想将权重分配给随机生成的数字，权重如下所示.

I want to assign weightings to a randomly generated number, with the weightings represented below.

  0  |  1  |  2  |  3  |  4  |  5  |  6
─────────────────────────────────────────
  X  |  X  |  X  |  X  |  X  |  X  |  X
  X  |  X  |  X  |  X  |  X  |  X  |   
  X  |  X  |  X  |  X  |  X  |     |   
  X  |  X  |  X  |  X  |     |     |   
  X  |  X  |  X  |     |     |     |   
  X  |  X  |     |     |     |     |   
  X  |     |     |     |     |     |   

最有效的方法是什么?

推荐答案

@Kerrek的回答很好.

@Kerrek's answer is good.

但是，如果权重的直方图不是全部都是小整数，则需要更强大的功能:

But if the histogram of weights is not all small integers, you need something more powerful:

将[0..1]划分为权重大小的间隔.在这里，您需要相对尺寸比例为7:6:5:4:3:2:1的细分.因此，一个间隔单位的大小为1/(7 + 6 + 5 + 4 + 3 + 2 + 1)= 1/28，间隔的大小为7/28、6/28，... 1/28岁

Divide [0..1] into intervals sized with the weights. Here you need segments with relative size ratios 7:6:5:4:3:2:1. So the size of one interval unit is 1/(7+6+5+4+3+2+1)=1/28, and the sizes of the intervals are 7/28, 6/28, ... 1/28.

这些构成概率分布，因为它们的总和为1.

These comprise a probability distribution because they sum to 1.

现在找到累积分布:

P        x
7/28  => 0
13/28 => 1
18/28 => 2
22/28 => 3
25/28 => 4
27/28 => 5
28/28 => 6

现在在[0..1]中生成一个随机的r编号，并通过查找最小的x(例如r <= P(x))在此表中查找它.这是您想要的随机值.

Now generate a random r number in [0..1] and look it up in this table by finding the smallest x such that r <= P(x). This is the random value you want.

可以通过二进制搜索来进行表查找，当直方图具有多个bin时，这是一个好主意.

The table lookup can be done with binary search, which is a good idea when the histogram has many bins.

请注意，您正在有效地构造逆累积密度函数，因此有时称为逆变换的方法.

Note you are effectively constructing the inverse cumulative density function, so this is sometimes called the method of inverse transforms.

这篇关于加权随机整数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！