如何生成[0, N)中的随机数

写程序的时候,经常会遇到这样的需求:已知rand函数,生成一个范围在[0, N)的随机数。 比如我们有15个球,随机选择一个,则此时N等于15。 在这个问题中,我们通常希望这个随机数是满足均匀分布(uniform distribution)的,即每个数字出现的概率是一样的。 还有一类随机数生成问题,是要求实现rand这个函数本身的,这类问题已经被广泛过,这篇文章不会讨论这类的问题。

之前看到的几乎所有的地方(包括我自己)都是这么写的:

1
int r = rand() % N;

后来校招面试百度的时候,一位叫戈君的面试官无意中告诉我这么写是错的,我回来想了一想,果然是不对的。 各位读者如果以前一直都是这么写的,不妨先不要继续看下去,自己思考一下错在什么地方。

为了说明错在哪里,我们举一个简单的例子: 我们假设rand()的返回的最大值是9,N等于7,那么rand()返回[0,6]时,直接返回该值;如果返回[7,9]时,则返回[0,2],我们可以看出,返回0的概率是2/10,因为rand()得到0和7都会使结果为0,同理1和2的概率也是2/10,但是[3,6]中的数概率为1/10。这显然不符合均匀分布的定义。

稍稍想想可以发现:问题出在了N不能整除rand()返回的范围,使得最后“少了一段”。 试想上述情况中N=5,就不会发生这种情况,每一个值出现的概率都是2/10。

为了解决这个问题,思路是这样的:假设rand()的返回值范围是[0, M),我们需要在这个范围划分出N个bucket,然后随机一个数,看这个数落到哪个bucket里,那么就返回这个bucket的标号。每份的bucket的长度L为M/N,那么这个范围中最后还剩余M%N。 如果rand() < M – M%N,那么就返回该值/ L;否则就重试一遍,直到达到上述条件。

用C++写出来代码是这样的:

1
2
3
4
5
6
7
8
9
10
typedef unsigned long long ull
ull bucket_size = M/N;
ull remain = M%N;
ull r;

do {
    r = rand();
} while (r >= M - remain);

return r/bucket_size;

这样返回值就是满足在[0,N-1]上的均匀分布。

另外,想到了一道面试题:函数rand5可以返回在[1,5]上的一个随机数,满足均匀分布,如何用这个rand5来实现一个rand7(即可以返回[1,7]上的一个随机数)?这个题的本质和上述思想是一致的,读者诸君不妨想想如何求解。