如何select一个项目的概率?

我有一个项目列表。 每个项目都有自己的概率。

任何人都可以提出一个algorithm来select一个项目的概率?

因此,每个商品都会存储一个标记其相对概率的数字,例如,如果您有3个商品,则其中一个应该是另外两个商品的两倍,那么您的商品列表将包含:

[{A,1},{B,1},{C,2}] 

然后总结清单的数字(在我们的例子中是4)。 现在生成一个随机数并select该索引。 int index = rand.nextInt(4); 返回数字,使索引在正确的范围内。

Java代码:

 class Item { int relativeProb; String name; //Getters Setters and Constructor } ... class RandomSelector { List<Item> items = new List(); Random rand = new Random(); int totalSum = 0; RandomSelector() { for(Item item : items) { totalSum = totalSum + item.relativeProb; } } public Item getRandom() { int index = rand.nextInt(totalSum); int sum = 0; int i=0; while(sum < index ) { sum = sum + items.get(i++).relativeProb; } return items.get(Math.max(0,i-1)); } } 
  1. 生成一个均匀分布的随机数。
  2. 迭代你的列表,直到访问元素的累积概率大于随机数

示例代码:

 double p = Math.random(); double cumulativeProbability = 0.0; for (Item item : items) { cumulativeProbability += item.probability(); if (p <= cumulativeProbability) { return item; } } 

假装我们有以下列表

 Item A 25% Item B 15% Item C 35% Item D 5% Item E 20% 

假设所有概率都是整数,并为每个项目分配一个“范围”,计算如下。

 Start - Sum of probability of all items before End - Start + own probability 

新号码如下

 Item A 0 to 25 Item B 26 to 40 Item C 41 to 75 Item D 76 to 80 Item E 81 to 100 

现在从0到100中select一个随机数。假设你select了32.在项目B的范围内select了32个。

MJ

你可以尝试轮盘select 。

首先,将所有概率相加,然后将所有概率按比例缩小1。 假设概率是A(0.4), B(0.3), C(0.25) and D(0.05) 。 然后可以在[0,1]范围内生成一个随机的浮点数。 现在你可以这样决定:

 random number between 0.00 and 0.40 -> pick A between 0.40 and 0.70 -> pick B between 0.70 and 0.95 -> pick C between 0.95 and 1.00 -> pick D 

你也可以用随机整数来做 – 也就是说你生成一个0到99之间的随机整数,然后你可以做出如上的决定。

在Ushman's , Brent's和@ kaushaya的答案中描述的algorithm在Apache commons-math库中实现。

看看EnumeratedDistribution类(groovy代码如下):

 def probabilities = [ new Pair<String, Double>("one", 25), new Pair<String, Double>("two", 30), new Pair<String, Double>("three", 45)] def distribution = new EnumeratedDistribution<String>(probabilities) println distribution.sample() // here you get one of your values 

请注意,概率之和不需要等于1或100 – 它将被自动标准化。

我的方法很简单。 生成一个随机数。 现在,由于您的项目的概率是已知的,只需遍历sorting的概率列表,并select其概率小于随机生成的数量的项目。

欲了解更多详情,请阅读我的答案。

一个缓慢而简单的方法是让每个成员根据其概率挑选一个随机数,并挑选出最具价值的一个。

比喻:

想象一下,需要select三个人中的一个,但他们有不同的概率。 你给他们不同的面额死亡。 第一人称骰子有4张脸,第二人称6,第三人称8。他们掷骰子,最大的胜利。

可以说我们有以下列表:

[{A,50},{B,100},{C,200}]

伪代码:

  A.value = random(0 to 50); B.value = random(0 to 100); C.value = random (0 to 200); 

我们select价值最高的那个。

上面的这个方法并不准确地映射概率。 比如说100就不会有两次50的机会。但是我们可以通过调整方法来做到这一点。

方法2

而不是从0到重量的数字,我们可以限制他们从以前的variables的上限增加当前的variables。

[{A,50},{B,100},{C,200}]

伪代码:

  A.lowLimit= 0; A.topLimit=50; B.lowLimit= A.topLimit+1; B.topLimit= B.lowLimit+100 C.lowLimit= B.topLimit+1; C.topLimit= C.lowLimit+200 

造成的限制

 A.limits = 0,50 B.limits = 51,151 C.limits = 152,352 

然后我们从0到352中select一个随机数,并将其与每个variables的限制进行比较,以查看随机数是否在其范围内。

我相信这个调整有更好的performance,因为只有一个随机世代。

在其他答案中有一个类似的方法,但是这种方法不要求总数为100或1.00。

Brent的答案是好的,但是它没有考虑在p = 0的情况下错误地select概率为0的项目的可能性。通过检查概率很容易处理(或者可能不在第一个项目中添加项目地点):

 double p = Math.random(); double cumulativeProbability = 0.0; for (Item item : items) { cumulativeProbability += item.probability(); if (p <= cumulativeProbability && item.probability() != 0) { return item; } } 

你可以使用茱莉亚代码:

 function selrnd(a::Vector{Int}) c = a[:] sumc = c[1] for i=2:length(c) sumc += c[i] c[i] += c[i-1] end r = rand()*sumc for i=1:length(c) if r <= c[i] return i end end end 

这个函数有效地返回一个项目的索引。