随机数

1 伪随机数

什么是随机数？通俗说法就是随机产生一个数，这个数预先不能计算出来，并且每个数字出现的概率是一样的。随机数必须满足以下两个条件：

• 不可计算性。即在随机数产生前，不能通过任何方式计算出来。
• 机会均等性。即需要保证每个数出现的概率是相等的。

在生活中，随机数产生其实并不难，比如通过掷骰子的方式就可以很容易获取一个随机数。但计算机产生随机数却并不容易。在编程中，我们经常调用随机数生成器函数，但其实产生的并不是真正的随机数，而是通过一定的算法计算出来的（不满足随机数的不可计算性），我们称它为伪随机数！

由于它具有类似随机的统计特征，在不是很严格的情况，使用软件方式产生伪随机相比硬件实现方式，成本更低并且操作简单、效率也更高！

2 随机数生成算法

前面提到伪随机数是通过一定的算法计算出来的，实现的算法有很多，但大多数都会基于一个随机种子生成的，随机种子是一个初始值，比如当前系统时间，然后基于该种子不断迭代生成不同的随机数。比如C语言中的stdlib中rand_r函数（用的glibc）实现如下：

/* This algorithm is mentioned in the ISO C standard, here extended for 32 bits. */
int
rand_r (unsigned int *seed)
{
  unsigned int next = *seed;
  int result;
 
  next *= 1103515245;
  next += 12345;
  result = (unsigned int) (next / 65536) % 2048;
 
  next *= 1103515245;
  next += 12345;
  result <<= 10;
  result ^= (unsigned int) (next / 65536) % 1024;
 
  next *= 1103515245;
  next += 12345;
  result <<= 10;
  result ^= (unsigned int) (next / 65536) % 1024;
 
  *seed = next;
 
  return result;
}

而Java中的Random类产生方法next()为：

protected int next(int bits) {
       long oldseed, nextseed;
       AtomicLong seed = this.seed;
       do {
           oldseed = seed.get();
           nextseed = (oldseed * multiplier + addend) & mask;
       } while (!seed.compareAndSet(oldseed, nextseed));
       return (int)(nextseed >>> (48 - bits));
   }

Java中还有一个更精确的伪随机产生器java.security.SecurityRandom, 它继承自Random类，其实现方法如下：

final protected int next(int numBits) {
       int numBytes = (numBits+7)/8;
       byte b[] = new byte[numBytes];
       int next = 0;
 
       nextBytes(b);
       for (int i = 0; i < numBytes; i++) {
           next = (next << 8) + (b[i] & 0xFF);
       }
 
       return next >>> (numBytes*8 - numBits);
   }

最近有一道和随机数相关的非常经典的算法题：已知一个rand7函数，该函数能够产生1～7的随机数，需要实现一个函数使其能够产生1～10的随机数。

显然调用一次是不能满足，必须多次调用组合！利用乘法原理，调用rand7() * rand7()可以产生1_{49的随机数，我们可以把结果模10（取个位数）得到0}9的数，再加1,即产生1~10的数。

但我们还需要保证随机数出现的机会均等性。显然1～49中，共有49个数，个位为0出现的次数要少1，不满足概率相等的条件。如果直接这样计算，2~10出现的概率要比1出现的概率大！

我们可以丢掉一些数字，比如不要大于40的数字，大于40的直接弃掉并重新产生，实现代码如下：

int rand10() {
    int ans;
    do {
        int i = rand7();
        int j = rand7();
        ans = i * j;
    } while(ans > 40);
    return ans % 10 + 1;
}

3 随机数应用–洗牌算法

随机数的用途非常广泛，比如取样、产生随机密码等。下面介绍使用随机数的一个经典应用–洗牌算法。洗牌大家都很熟悉，在打牌时，为了保证下次抓牌的随机性和公平性，我们打完每一局牌都需要重新洗牌。抽象成模型就是把一个列表顺序随机打乱。

我们可能遇到比较多的情况是把一个无序的列表排序成一个有序列表。而洗牌算法（shuffle）则是一个相反的过程，它是把一个有序的列表（当然无序也无所谓）变成一个顺序完全随机的无序的列表。同样需要满足两个条件：

• 不可计算性。即打乱之前不能通过其它任何方式得出随机列表。
• 机会均等性。列表的每个元素出现在任意索引位置的概率是相等的。

当然我们也有个前提是，我们已经实现了随机数生成算法。

我们假设有1～100共100个无重复数字列表。

很容易想到的一种暴力求解算法：

• 创建一个与原列表长度一样的新列表。然后从第一个数开始，利用随机生成器产生1～100的随机数，比如产生88,则看在新列表中第88个位置有没有被占用，如果没有被占用则把当前数放到第88位置，如果已经占用，则重新产生随机数，直到找到有空位置为止！

这个方法实现了洗牌算法，但效率非常低，空间复杂度是O(n)，时间复杂度是O(kn)，越到后面冲突概率越大，越难找到空位置，大量时间浪费在求随机数和找空位置上。

第二种方案，基于交换思想：

• 依次遍历列表的所有元素，设当前遍历的数的索引为i，利用随机函数生成器产生1～100的随机数，比如产生88，则交换第i张牌和第88张牌。

该方案是原地操作（空间复杂度为O(1))，并且避免了位置冲突问题。但是否能够保证每个数的放置满足机会均等性呢？

我们知道n张牌，利用随机数产生N种情况，要满足N中情况出现概率相等，则必须满足N能够整除n，这样就能给予每个牌以N/n的机会，这是必须满足必要条件。想象下如果N不能整除n，一定不能保证n出现的概率相同。我们可以通过简单的例子解释下原因：

• 假设我们的随机数能够随机生成1-8共8个数，我们需要得到0/1的随机数，则我们只需要规定生成的偶数为0，奇数为1即可。
• 假设我们的随机数能够生成1-9共9个数，我们需要得到0/1的随机数，因为9不能被2整除，多出的一个数到底归为0呢，还是1呢。

我们知道n个不重复的数共有100!全排列组合情况，而调用n次随机函数，每次生成1-n之间的整数，共可以产生n^n种组合情况。而n^n一定不能整除n!，想想为什么？

我们的第二种方案，每次都随机产生1-100的数，重复调用100次，相当于有100^100种可能情况，而我们的列表只有100！种组合可能，显然不能满足机会均等性。

我们可以利用第二种方法改进，每次不是产生1_{100的随机数，而是1}i的数字，则共有n!种情况，即N=n!，这也就是经典的Fisher-Yates_shuffle算法，大多数编程语言库都使用了该算法实现洗牌算法。

其中Java中Collections库实现如下：

public static void shuffle(List<?> list, Random rnd) {
       int size = list.size();
       if (size < SHUFFLE_THRESHOLD || list instanceof RandomAccess) {
           for (int i=size; i>1; i--)
               swap(list, i-1, rnd.nextInt(i));
       } else {
           Object arr[] = list.toArray();
 
           // Shuffle array
           for (int i=size; i>1; i--)
               swap(arr, i-1, rnd.nextInt(i));
 
           // Dump array back into list
           // instead of using a raw type here, it's possible to capture
           // the wildcard but it will require a call to a supplementary
           // private method
           ListIterator it = list.listIterator();
           for (int i=0; i<arr.length; i++) {
               it.next();
               it.set(arr[i]);
           }
       }
   }

以上静态方法还考虑了列表不支持随机访问的情况，比如链表，此时需要先拷贝元素到一个新的数组中，然后基于新数组执行shuffle算法。

C++中STL库实现如下：

// random_shuffle  
template <class _RandomAccessIter>
inline void random_shuffle(_RandomAccessIter __first,
                           _RandomAccessIter __last) {
  __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator);
  if (__first == __last) return;
  for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
    iter_swap(__i, __first + __random_number((__i - __first) + 1));
}
 
template <class _RandomAccessIter, class _RandomNumberGenerator>
void random_shuffle(_RandomAccessIter __first, _RandomAccessIter __last,
                    _RandomNumberGenerator& __rand) {
  __STL_REQUIRES(_RandomAccessIter, _Mutable_RandomAccessIterator);
  if (__first == __last) return;
  for (_RandomAccessIter __i = __first + 1; __i != __last; ++__i)
    iter_swap(__i, __first + __rand((__i - __first) + 1));
}

如何测试洗牌算法具有随机性呢？其实很简单，调用洗牌算法N次，牌数为n，统计每个数字出现在某个位置的出现次数，构成一个矩阵n * n,如果这个矩阵的值都在N/n左右，则洗牌算法好。比如有100个数字，统计一万次，则每个数字在某个位置的出现次数应该在100左右。

4 洗牌算法应用

洗牌算法的应用也很广，比如三国杀游戏、斗地主游戏等等，还有我们播放器的随机播放功能。当然并不是所有的播放器都使用了随机洗牌算法，有些播放器的随机播放是每次产生一个随机数来选择播放的歌曲，这样就有可能还没有听完所有的歌前，又听到已经听过的歌。如何判断使用的是不是洗牌算法呢？ 很简单，如果点上一首还能回去，则可能利用的是洗牌算法，而如果是另一首歌，则肯定不是。