如何 select 以等概率从不同范围取值

Question

提供不同的范围，select每个值的概率相等。就像说 var 'a' 可以有 { [10,20],40,[70,100]...} (given) 之间的值。每个 selected 值由提供的约束应该有相同的概率。如何在 C 中获取随机值？

Answer 1

给每个范围相等的概率：

设 N 为您在 problem-set 中定义的范围数。范围 { R₀, R₁, R₂ ... R_{N -1} }，索引从 0.
生成一个随机数，RandValue mod N选择一个范围。在 C 中，模运算符是 %，得到整数余数。
选择的范围只是一个数字吗？ （如您示例中的 40）
- 3.1 是的，那么你的随机值就是那个数字
- 3.2 不，这是一个范围。在所选范围内找到一个随机值。

给所有范围内的每个值相等的概率机会：

设 N 为所有范围内值的数量。
将每个 value 映射到一个 index，值 { V₀，V₁，V₂ ... V_N-1 }, 索引从 0.
使用 hash-tables 进行快速查找。此外，您还可以处理重叠范围。
生成一个随机数，RandValue mod N选择一个value-index。
在 hash-table 中查找针对索引的映射值。

另外请注意，如果范围太大，hash-table 可能会变得很大。在这种情况下，您可能必须 merge overlapping/consecutive （如果有） 范围并维护排序（按 value-index）列表（结构数组）范围并分配 index-ranges。使用二进制搜索找到 random-index 的范围。范围偏移（start/end 值和索引）应该给出给定 random-index.

的最终值

PS：这是针对 C 项目中随机性的简单实现。我相信所有的随机性都是确定性的。

编辑：我同意，有 modulo-bias & 拒绝超出 (RAND_MAX - RAND_MAX % N) 的值。

Answer 2

简单的解决方案：

do
   r=rand();
until (is_in_range(r));

它一点也不高效，尤其是它不受运行ning 时间的限制。但它应该有效。

有时简单而愚蠢的解决方案就足够了。

（一旦你开始做 r=rand()%limit; 之类的事情，你就会开始引入偏斜概率。想象一下做 r=rand()%((RAND_MAX/2)+1);。return 任何低于 RAND_MAX/2 的可能性是两倍作为 RAND_MAX/2。有关详细信息，请参阅 this answer。 )

为了提高性能，可以像@Jakob Stark 暗示的那样做一些事情：

for(limit=1;limit<top_of_range;limit<<=1)
       ;  // Find the smallest power-of-two larger than the top_of_range
do
      r=rand()%limit;
while(!(is_in_range(r));

仍然不能保证到运行，但是...

如何 select 以等概率从不同范围取值

How to select value from different ranges with equal probability

c

random

probability