加权随机数 [英] Weighted random numbers

问题描述

我想实现一个加权的随机数。我目前刚刚撞我的头靠在墙上，不明白这一点。

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.

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