转载

一道随机数题目的求解

一道随机数题目的求解有这样一道算法题：

给定一个能够生成均匀1~5随机枚举数的函数，请设计一个能够生成均匀1~7随机枚举数的函数。

就是说，有一个生成随机数的函数rand5，可能返回1、2、3、4、5这5个枚举值，其中每个值被返回的概率都是严格的1/5，现在需要设计一个类似的随机数函数rand7，可能返回1、2、3、4、5、6、7这几个枚举值，每个值被返回的概率都是严格的1/7。

先掩卷思考，脑海中浮现的思路包括：

调用rand5的结果除以5，再乘以7，这样的结果范围为7/5~7，并非所希望的结果；
反复调用rand5函数7次，结果再除以5，这样的结果范围为也为7/5 ~ 7，并非所希望的结果。

如果题目反过来呢，已知rand7，求rand5呢？

那我可以先调用rand7，看看结果，如果结果为1~5，直接返回；如果结果为6、7，继续重试不就得了？

那再回到现实，怎么根据rand5求rand7？

如果rand5 * 2的结果，范围是2~10，用上面类似的办法只能得到2~7的值，无法得到1，不合题意。

但是依然得到了一种启发，调用一次rand5，结果的各种可能性有5种，要映射到rand7的7种结果可能性，是不现实的。但是如果扔两次，在不考虑去重的情况下，结果有5*5=25种可能，用某种方式映射并保留那最终的7种可能性，却是一个值得去尝试的思路。

想到了5*5，于是尝试建立二维数组arr[5][5]，那么数组的每一个元素都可以表示一种结果的可能性，在数组中取前7个元素，分别映射到1~7：

[1, 2, 3, 4, 5] [6, 7, 0, 0, 0] [0, 0, 0, 0, 0] [0, 0, 0, 0, 0] [0, 0, 0, 0, 0]

于是调用rand5两次，分别得到横坐标i和纵坐标j，如果arr[i][j]>0，则保留，否则重试。

这样的方法还不完美，因为25个数里面只有7个是有效的，大部分情况下都只能重试了，效率太低。

于是，在这个二维数组里面不止保留前7位，而是尽可能多地保留了所有7的完整倍数：

[1, 2, 3, 4, 5] [6, 7, 1, 2, 3] [4, 5, 6, 7, 1] [2, 3, 4, 5, 6] [7, 0, 0, 0, 0]

这样一来，大部分情况下，都会命中大于0的元素。

那就写出代码：

public class R {  private static Random random = new Random();  private static int[][] arr = new int[][]{   {1,2,3,4,5},   {6,7,1,2,3},   {4,5,6,7,1},   {2,3,4,5,6},   {7,0,0,0,0}  };   public static int rand5(){   random.setSeed(System.nanoTime());   return random.nextInt(5) + 1;  }    public static int rand7() {   int i = rand5() - 1;   int j = rand5() - 1;      if (i == 4 && j >= 1)    return rand7();    return arr[i][j];  } }

再写个main函数测试一下：

Map<Integer, Integer> counter = new HashMap<Integer, Integer>();  for (int i = 0; i < 10000000; i++) {  int key = rand7();  Integer val = counter.get(key);  if (null == val)   val = 0;  val++;  counter.put(key, val); }  for (Map.Entry<Integer, Integer> entry : counter.entrySet()) {  System.out.println(entry.getKey() + ": " + entry.getValue()); }

重复测试一千万次，但是从结果看，分布却并不足够随机：

1: 1476605 2: 1764393 3: 1274549 4: 1219960 5: 1454842 6: 1425833 7: 1383818

重复测试了几次，都是输出2的情况居多。就这个数据量而言，我觉得这不是巧合。

为了让这个可能的差异更加明显，我把从rand5求rand7改成了从rand2求rand3：

public class R {  private static Random random = new Random();  private static int[][] arr = new int[2][2];  static {   arr[0][0] = 1;   arr[0][1] = 2;   arr[1][0] = 3;   arr[1][1] = 0;  }   public static int rand2(){   random.setSeed(System.nanoTime());   return random.nextInt(2) + 1;  }    public static int rand3() {   int i = rand2() - 1;   int j = rand2() - 1;    if (i == 1 && j == 1)    return rand3();    return arr[i][j];  } }

再同样测试一千万次，结果却大跌眼镜：

One: 5043264 Two: 2472499 Three: 2484237

居然有一倍的差异。

怎么回事呢？我开始怀疑Java的这个伪随机函数得出的结果（在计算机的世界里要实现绝对随机是不可能的）不足够随机，于是写了个程序调用一千万次Java的伪随机函数来看结果：

Map<Integer, Integer> counter = new HashMap<Integer, Integer>();  for (int i = 0; i < 10000000; i++) {  random.setSeed(System.nanoTime());  int key = random.nextInt(7) + 1;    Integer val = counter.get(key);  if (null == val)   val = 0;  val++;  counter.put(key, val); }  for (Map.Entry<Integer, Integer> entry : counter.entrySet()) {  System.out.println(entry.getKey() + ": " + entry.getValue()); }

从结果来看分布非常均匀：

1: 1429576 2: 1425422 3: 1427902 4: 1427424 5: 1429457 6: 1430664 7: 1429555

一下子觉得百思不得其解。

于是我重新审视自己的思路，还是觉得没有什么问题。虽然总结果最初有25个，但是前21个的结果每个得到的可能性都是一致的，最后四个丢掉并重来，继续的测试依然是能保证结果概率均等的。本质上这种方式在统计学上面叫做“Reject Sampling”。

我请教了一下数学家@万精油墨绿，他说思路是没什么问题的，有问题的话，只能是代码的问题。

其实还有一种方法，本质上也是类似的，即根据：

5 * (rand5()-1) + rand5()

上面这个式子的结果可以得到从1到25所有的结果，并且显而易见这25个结果出现时，这两个rand5()都可以被唯一确定返回值，因此他们出现的概率都是彼此相等的。于是可以根据上面的公式，在结果大于3*7=21的时候重新计算，否则则返回除以7的余数即可：

public class R {  private static Random random = new Random();   public static int rand5() {   random.setSeed(System.nanoTime());   return random.nextInt(5) + 1;  }   public static int rand7() {   int i = rand5();   int j = rand5();    int res = 5 * (i - 1) + j;    if (res > 21)    return rand7();    return res % 7 + 1;  } }

同样跑了几次测试，每次测试一千万条数据，这次发现这个偏大的数跑到3上面去了：

1: 1383566 2: 1486463 3: 1748051 4: 1275854 5: 1219712 6: 1451438 7: 1434916

这么一来反而有点开窍的感觉了，我觉得是不是因为Java的伪随机数生成的方法，生成的数不足够随机呢？虽然看起来是随机的，但是那也只是看起来而已。当用“小随机”去生成“大随机”的时候，那些不随机的缺陷被放大了。而比较rand2生成rand3，和rand5生成rand7，明显是前者“放大”的倍数更大，因此最后得出的结果中，“随机性”显得差。

为了进一步检验这种猜想，我开始考虑能否让随机数的种子变化更大。因为目前使用的随机数种子是System.nanoTime()，这个方法看似纳秒，其实也只是：

Returns the current value of the most precise available system timer, in nanoseconds.

我想在我的实验中它远比毫秒精确，但是也只是保证了尽可能精确而已。

那好，要验证或者说部分验证这样的猜想，现在假设这样的猜想是正确的，那么可以得出这样的推论：