转载

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

写程序的时候，经常会遇到这样的需求：生成一个范围在[0, N)的随机数。比如我们有15个球，随机选择一个，则此时N等于15。在这个问题中，我们通常希望这个随机数是满足均匀分布（uniform distribution）的，即每个数字出现的概率是一样的。

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

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++写出来代码是这样的：

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]上的一个随机数）？这个题的本质和上述思想是一致的，读者诸君不妨想想如何求解。

原文 http://lifeofzjs.com/blog/2017/01/07/how-to-generate-uniform-distribution/

正文到此结束