问题描述
我想实现一个加权的随机数。我目前刚刚撞我的头靠在墙上，不明白这一点。
I'm trying to implement a weighted random numbers. I'm currently just banging my head against the wall and cannot figure this out.
在我的项目（德州扑克手的范围，主观的所有股权分析），我使用Boost的随机-functions。所以，让我们说，我要挑1和3之间的随机数（所以是1，2或3）。 Boost的梅森倍捻机发生器的工作原理是这一个魅力。不过，我想进行加权比如像这样的选秀权：
In my project (Hold'em hand-ranges, subjective all-in equity analysis), I'm using Boost's random -functions. So, let's say I want to pick a random number between 1 and 3 (so either 1, 2 or 3). Boost's mersenne twister generator works like a charm for this. However, I want the pick to be weighted for example like this:
1 (90% chance to be picked up)
2 (56% chance to be picked up)
3 ( 4% chance to be picked up)升压是否有某种此功能？
Does Boost have some sort of functionality for this?
推荐答案
有是随机的，选择一个项目一个简单的算法，其中项目具有个体重量：
There is a straightforward algorithm for picking an item at random, where items have individual weights:
1）计算所有的权重的总和
1) calculate the sum of all the weights
2）挑选的随机数为0或更大且小于权重的总和
2) pick a random number that is 0 or greater and is less than the sum of the weights
3）通过在一个时间的项目之一，从您的随机数减去自己的体重，直到你获得该项目所在的随机数小于该项目的体重
3) go through the items one at a time, subtracting their weight from your random number, until you get the item where the random number is less than that item's weight
伪code说明这一点：
Pseudo-code illustrating this:
int sum_of_weight = 0;
for(int i=0; i<num_choices; i++) {
sum_of_weight += choice_weight[i];
}
int rnd = random(sum_of_weight);
for(int i=0; i<num_choices; i++) {
if(rnd < choice_weight[i])
return i;
rnd -= choice_weight[i];
}
assert(!"should never get here");
这应该是简单的，以适应您的提升和容器等。
This should be straightforward to adapt to your boost containers and such.
如果你的权重很少会改变，但你经常随机选择一个，只要你的容器存储指向的对象或超过几十项长（基本上，你必须来分析知道，如果这有助于或妨碍），再有就是一个优化：
If your weights are rarely changed but you often pick one at random, and as long as your container is storing pointers to the objects or is more than a few dozen items long (basically, you have to profile to know if this helps or hinders), then there is an optimisation:
通过存储在每个项目的累计权重和可以使用挑对应挑项目体重。
By storing the cumulative weight sum in each item you can use a binary search to pick the item corresponding to the pick weight.
如果您不知道列表中的项目数量，然后有一个名为可适于进行加权。
If you do not know the number of items in the list, then there's a very neat algorithm called reservoir sampling that can be adapted to be weighted.
这篇关于加权随机数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！