一道随机数题目的求解

有这样一道算法题：

给定一个能够生成均匀 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 + rand5 的结果，范围是 2~10，用上面类似的办法只能得到 2~7 的值，无法得到 1，不合题意。

([2019-4-5] 有人说，那可以把上面的结果减 1 不就行了？即 rand5 + rand5 – 1，取得的数的范围是 1~9，舍弃掉 8、9，似乎是可以了，但是仔细想想还是错的：以舍弃掉的这个 9 为例，要得到它必须两次 rand5 都得是 5，因此概率就是 1/5*1/5=1/25，这个概率明显是低于单个数值的平均概率的。也就是说，这种方法得到 1~7 中的每个数并非是等可能的)

但是依然得到了一种启发，调用一次 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.

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

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

1. 如果随机数种子换成 System.currentTimeMillis()，也就是说，换成毫秒，那么最后的结果应该是更不随机；
2. 如果我在每次取随机数之前休息几毫秒，使得每两次之间的时间种子差异增大，应该能够看到最终的结果随机性增加。

（注，我测试的版本下 JDK 对于设置的种子的处理方式是：seed = (seed ^ 0x5DEECE66DL) & ((1L << 48) -1)。）

好吧，现在来验证第一条，为了尽可能使得结果明显，使用 rand2 生成 rand3 的那个方案。把使用纳秒作为随机数种子改成使用毫秒作为随机数种子，结果居然是：

One: 10000000
Two: 0
Three: 0

换言之，二维数组中横坐标和纵坐标居然在一千万次测试当中，得到的都是一样的结果，即绝大多数情况下求 i 和 j 的操作都在同一个毫秒量级内完成。

现在来验证第二条，在每次取随机数前，休眠 3 毫秒，当然，这个 3 毫秒肯定也是不精确的 3 毫秒。为了在增加休眠时间的情况下，能够在我的耐心时间范围内得到最终结果，我没法测试一千万次了，我的测试用例改成了测试一万次，结果为：

One: 3691
Two: 3103
Three: 3206

果然，分布的均匀性要好了很多。

问题还没完，为了尽可能消除这种种子相似所带来的伪随机性，其实可以只初始化一遍种子，然后在迭代方法内部不断调用 Random 的 nextInt 方法就好了，这也是在这种情形下更加合理的使用随机数生成器的方式：

public class R {
	private static Random random = new Random(System.nanoTime());
	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(){
		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];
	}

	public static void main(String[] args) {
		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: 1428864
2: 1429574
3: 1427055
4: 1429929
5: 1429162
6: 1426933
7: 1428483

还蛮好玩的。

文章未经特殊标明皆为本人原创，未经许可不得用于任何商业用途，转载请保持完整性并注明来源链接 《四火的唠叨》