如何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)); } }
- 生成一个均匀分布的随机数。
- 迭代你的列表,直到访问元素的累积概率大于随机数
示例代码:
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
这个函数有效地返回一个项目的索引。