不平衡的随机数生成器

Question

我需要从一个升序数组中选出一个元素。越小的元素被认为是更好的选择。因此，如果我从数组的开头选择一个元素，它被认为是更好的选择。但与此同时，我不希望选择是确定性的，而且总是相同的元素。因此，我正在寻找一个随机数生成器，它可以在范围[0，n]内产生数字，但是数字越小，它被产生的几率就越大。

我想到了以下方法：

num = n;
while(/*the more iteration the more chance for smaller numbers*/)
  num = rand()%num;

我想知道是否有更好的解决方案。
我查看了一些类似的问题，但它们通常涉及随机数生成的细节。我正在寻找一个针对这种特定类型的随机数生成的解决方案，无论是算法还是提供它的库。

- atoMerz

---

http://stackoverflow.com/questions/4207545/weighted-random-number-generation - Robert Harvey

Answer 1

生成一个随机数，取名为x，范围在[0,n)内，然后再生成一个随机浮点数，取名为y，范围在[0,1]内。接着将x的y次方并使用向下取整函数，即可得到所需的数字。

int cust(int n)
{
  int x;
  double y, temp;
  x = rand() % n;
  y = (double)rand()/(double)RAND_MAX;
  temp = pow((double) x, y);
  temp = floor(temp);
  return (int)temp;
}

更新：下面是调用上述函数10次时的一些示例结果，其中n = 10、20和30。

2 5 1 0 1 0 1 4 1 0

1 2 4 1 1 2 3 5 17 6

1 19 2 1 2 20 5 1 6 6

- vidit

---

谢谢，这可能有效，但是有一个问题：如何在C++中生成[0,1]范围内的数字？(rand()%n)/(float)n？ - atoMerz

从0到n的数字：(double)rand() / ((double)RAND_MAX * n) - Tomas

@AtoMerZ- 这将以较高概率生成随机数。 - vidit

再次感谢。这似乎是一个更好的解决方案，因为它只调用了一次rand()函数。我会等待一段时间以获取更多答案，如果没有更好的解决方案出现，我会接受这个方案。 - atoMerz

请注意，无论 n 的值如何，n - 1 在平均每 RAND_MAX 次试验中只会出现一次，这可能比您想要的要小得多（在我的机器上，RAND_MAX 是 2**31-1，约为 20 亿）。您可能希望探索解决这种急剧下降的方法。 - Aaron Dufour

Answer 2

我想到的简单临时方法是使用标准随机生成器，但重复索引。因此，在数组中：

0, 0, 0, 1, 1, 2, 3

很可能较小的元素会被选中。
我不确定您需要什么。您也可以定义自己的分布，或者使用一些随机数生成库。但建议的方法简单易配置。
更新2：您不必显式生成数组。对于大小为1000的数组，您可以从区间[0,1000000]生成随机数，然后配置所选值的自己的分布：例如，长度为1200的间隔用于较小的值（0-500），长度为800的间隔用于较大的值（500-1000）。主要的一点是这种方式可以轻松配置概率，而且您不必重新实现随机数生成器。

- default locale

---

如果我的数组里有大约1000个数字，那么你提供的方案几乎是不可能实现的。 - atoMerz

数组只是一个例子。主要的重点是改变较小值的间隔。请参见Update2。 - default locale

这绝对是实现非均匀分布（特别是加权分布）的最佳解决方案。它需要最少的计算时间并提供完全的灵活性。 - Neowizard

那么更大的间隔=更多的机会吗？ - atoMerz

+1 谢谢，总的来说这是一个不错的解决方案，但我认为对于这个特殊情况，我的方案更简单，需要更少的配置。 - atoMerz

谢谢，我只是提出了一个建议，对于这种特殊情况，我不知道什么更合适。 - default locale

Answer 3

使用适当的随机分布，例如指数分布的四舍五入结果。选择符合需求的分布，记录所使用的分布，并找到一个好的实现。如果可以使用GNU公共许可证下的代码，则可以使用优秀的GNU科学库（GSL），或者尝试Boost.Random。

- thiton

---

我非常确定我仅仅理解了Boost.Random。其他的是什么？ - atoMerz

@AtoMerZ：我扩展了这些缩写词。 - thiton

Answer 4

两个工具可以解决许多随机分布需求

1）您已经拥有的均匀随机数生成器

2）以及一个将均匀值映射到目标分布的函数

我现在得去城里了，但我回来后会写几个例子并附上图纸。

在相关问题中讨论了一些有价值的方法和思路（更多关于生成正态伪随机数的内容）

- Mark Essel