等概率产生 [1-7] 的随机数

文章目录

1. [准备阶段] 产生1-5的随机数Ranom类Math.random()时间戳 2. 解决一误区解决思考探究 3. 解决二最后一次不是等概率 4. 拓展

1. [准备阶段] 产生1-5的随机数

Java中产生随机数的方法主要有三种：

new Random()Math.random()currentTimeMillis()

Ranom类

边界为rand.nextInt(MAX - MIN + 1) + MIN;

public static void randFive(int[] arr) { Random random = new Random(); for (int i = 0; i < arr.length; i++) { arr[i] = random.nextInt(5) + 1; } }

Math.random()

【缺陷】：很难凑成既包括0又包括5的范围，只能是[0, 4]或者[0+1，4+1]

public static void randFiveII(int[] arr) { int max = 5, min = 1; for (int i = 0; i < arr.length; i++) { arr[i] = (int) (Math.random() * 5 + 1); } }

时间戳

【缺陷】：放入循环中产生，由于CPU执行速度快，产生连续的随机数是相同的，适合产生单个

public void randFiveIII() { int max = 100, min = 1; long randomNum = System.currentTimeMillis(); int ran = (int) (randomNum % (max - min) + min); //循环同一时间会产生相同的数 System.out.print(ran); }

2. 解决一

误区

对randFive产生的每一个rand % 3再相加，但是并不是等概率的！

public static void main(String[] args) { int[] arr_seven = new int[10]; for (int i = 0; i < arr_seven.length; i++) { arr_seven[i] = getRandomNumSeven(randFive()); } } //不是等概率 public static int getRandomNumSeven(int randNum) { return randNum + (randNum % 3); }

【原因】：

randFive() 能够等概率生成 1-5 之间的整数，1,2,3,4,5 生产的概率均为 0.2、

而rand()%3 产生0的概率是1/5，而产生1和2的概率都是2/5，所以这个方法产生6和7的概率大于产生5的概率。

如果randFive是产生1-10，是等概率吗？

并不是。比如对于 6来讲（4+2， 2+4， 3+3），它被生成的生成的概率比1 （1+0，0+1）要大。因为6有3种组合，而1只有2种组合

所以，对原来randFive产生的1-5的随机数，不能用加减乘除来得到getRandomNumSeven

解决

randFive，来构造一个更大的范围。使得范围里每一个值被生成的概率是一样的，而且这个范围是7的倍数。

先产生一个均匀分布的 0， 5， 10， 15， 20的数再产生一个均匀分布的 0， 1， 2， 3， 4 的数。相加以后，会产生一个 0到24的数，而且每个数（除0外）生成的概率是一样的只取 1 - 21 这一段，和7 取余以后+1就能得到完全均匀分布的1-7的随机数了

获得每个数的次数（概率）相等。即每个数只能由一种组合得到

/** * 调用randFive()来 等概率 产生 1-7 * @return */ public static void main(String[] args) { // 测试统计 Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < 1000000; i++) { int temp = getRandomNumSeven(); if (map.containsKey(temp)) { map.put(temp, map.get(temp) + 1); } else { map.put(temp, 1); } } map.forEach((key, value) -> { System.out.println(key + " -- 出现次数:" + value); }); } public static int getRandomNumSeven() { while (true) { int randLowSeven = (randFive() - 1) * 5 + randFive(); if(randLowSeven <= 21) { return randLowSeven % 7 + 1; } }

测试 100W次 出现的结果：

Python测试：

import numpy def randFive(): return numpy.random.randint(1, 6) # 随机1到5，不包括右端点6 def getRandomNumSeven(): while True: randLowSeven = randFive() + 5 * (randFive() - 1) # 产生均匀的1-25 if randLowSeven <= 21: # 只取1-21 return randLowSeven % 7 + 1 res = [0] * 8 for i in range(1000000): rnd = getRandomNumSeven() res[rnd] += 1 print(res[1:]) # 随机生成多次，验证1到7的出现次数是否均匀 # res[1:]为[142980, 142709, 142939, 142875, 142398, 143277, 142822],是均匀的

思考探究

为什么是 (randFive() - 1) * 5 + randFive() ，为什么是弃掉大于21的数再模7

因为要先通过两次调用，将已有的随机数函数扩大范围。 (randFive() - 1) * 5 + randFive()，本身[1-7]的范围用randFive()的函数等概率产生，5个数凑7个数一定是不公平的。所以要通过randFive()来放大取值范围；

但是，放大了取值范围，5等概率扩大的数的范围在[1, 25]（假设此时已对[0, 24] + 1），多了22\23\24\25 三个数，如果去去除，则

22 % 7 = 1 23 % 7 = 2 24 % 7 = 3 25 % 7 = 4

那么1、2、3、4就不是等概率了，所以只取[1, 21]。由于产生扩大的每个数时是等概率的，那么在去除25 % 7 = 4后，三个子集中每个元素依然是等概率的。

---

3. 解决二

这种实现前6个是等概率的，最后一个与前6个出现的次数差距很大，存在问题。

算法思路是：

通过(randFive() * 5 + randFive()) <= 25产生 6 7 8 9 10 11 …… 26，27 28 29 30 这25个数，每个数的出现机率相等只需要前面21个数，所以舍弃后面的4个数将 [6 7 8 ]转化为 1，[9 10 11] 转化为 2，……，[24 25 26] 转化为 7。公式是 (randLowSeven-3) / 3 public static int getRandomNumSevenII() { int randLowSeven = 0; while ((randLowSeven = randFive() * 5 + randFive()) > 26); return (randLowSeven - 3) / 3; }

最后一次不是等概率

但是，这样写却是不正确的。导致最后一次不公平。

因为出现 > 26 的情况，说明 randFive() * 5 有很大概率等于25，从而又导致while之后的randLowSeven有很大机率很大，破坏了平衡性。

public static int getRandomNumSeven() { int randLowSeven = 0; while (true) { if((randLowSeven = randFive() * 5 + randFive()) <= 25) { return (randLowSeven - 3) / 3; } } }

4. 拓展

就是对【方法一】的拓展，由之前的(randFive - 1)产生每一位5进制数，然后将``randLowSeven%7+1`就得到了均匀分布于1到7的算法.

那么现在将其转为m进制的数，等概率表示**[1 - n]** 之间的范围

public class Main { public static int rand1ToM(int m) { return (int) (Math.random() * m) + 1; } //产生1-n的随机函数 public static int rand1ToN(int n, int m) { int[] nMSys = getMSysNum(n - 1, m); int[] randNum = getRanMSysNumLessN(nMSys, m); return getNumFromMSysNum(randNum, m) + 1; } // 把value转成m进制的数 public static int[] getMSysNum(int value, int m) { int[] res = new int[32]; int index = res.length - 1; while (value != 0) { res[index--] = value % m; value = value / m; } return res; } // 等概率随机产生一个0~nMsys范围上的数，只不过是m进制表达的 public static int[] getRanMSysNumLessN(int[] nMSys, int m) { int[] res = new int[nMSys.length]; int start = 0; while (nMSys[start] == 0) { start++; } int index = start; boolean lastEqual = true; while (index != nMSys.length) { res[index] = rand1ToM(m) - 1; if (lastEqual) { if (res[index] > nMSys[index]) { index = start; lastEqual = true; continue; } else { lastEqual = res[index] == nMSys[index]; } } index++; } return res; } // 把m进制的数转成10进制 public static int getNumFromMSysNum(int[] mSysNum, int m) { int res = 0; for (int i = 0; i != mSysNum.length; i++) { res = res * m + mSysNum[i]; } return res; } public static void main(String[] args) { Map<Integer, Integer> map = new HashMap<>(); System.out.println("randM 等概率产生 [1 - n]的随机数: "); for (int i = 0; i < 1000000; i++) { // 测试方法二 int temp = rand1ToN(4, 5); if(map.containsKey(temp)) { map.put(temp, map.get(temp) + 1); } else { map.put(temp, 1); } } map.forEach((key, value) -> { System.out.println(key + " -- 出现次数:" + value); }); } }