等概率随机函数设计技巧

秒速五厘米 2023-09-27 18:42 117阅读 0赞

#### 文章目录 ####

*  1. 关于Math.random()函数
 *  2. 用1 ~ 5的随机函数加工出1 ~ 7的随机函数
 *  3. LeetCode 470. 用 Rand7() 实现 Rand10()
 *  4. 把不等概率随机函数变成等概率随机函数
 *  5. 用a ~ b的随机函数加工出c ~ d的随机函数

## 1. 关于Math.random()函数 ##

Java 中 `Math.random()` 函数是等概率返回区间 `[0,1)` 中的任意一个浮点数, 即 `x < 1` 情况下, 调用这个api, 得到 `[0,x)` 范围上的数的概率就是 `x`; 那么, 如果想要将 `x < 1` 情况下, 生成的`[0,x)` 范围上的数的概率调整成 `x ^ 2`, 应该怎么实现?

*  实现思路:

由于生成 `[0,x)` 的概率是 `x` , 那么调用两次 `Math.random()`, 得到的两个值中, 如果较大的那个值也在`[0,x)`区间内, 那么此时两次调用生成 `[0,x)` 范围上的数字的概率就为 `x ^ 2`了; 要注意这两次调用都必须在 `[0,x)` 区间内 (因为任意一次在 `[x,1)` 都会导致返回值不在 `[0,x)` 上).

*  代码实现:

/**
     * rangom 函数生成的任意一个随机数都在 [0,1) 范围内,
     * 这个函数让 [0, x) 范围上出现的数字概率由原来的 x 调整为 x^2
     */
    public static double xToXPower2() {
        
        // 调用两次,取到两次的的最大值,这样要想得到[0, x)范围内值就需要两次调用都在范围内
        // 一次得到的概率是x, 那么两次都要得到范围内的值的概率就是 x^2;
        return Math.max(Math.random(), Math.random());
    }

*  测试代码:

public static void main(String[] args) {
        
        // 测试次数
        int testTimes = 10000000;
        // random函数的测试
        int count = 0;
        double x = 0.27;
        for (int i = 0; i < testTimes; i++) {
        
            if (xToXPower2() < x) {
        
                count++;
            }
        }
        // 以下两个数值应该大小接近一致
        System.out.println(count / (double) testTimes);
        System.out.println(Math.pow(x, 2));
    }

*  测试结果:

![img][]

可以看到结果是相近的.

## 2. 用1 ~ 5的随机函数加工出1 ~ 7的随机函数 ##

假设我们有一个随机函数 `f()`, 这个函数可以等概率返回 `[1,5]` 中的一个数, 请实现只利用 `f()` 函数而不引入其他随机函数, 得到一个等概率返回 `[1,7]` 中任意一个数的函数.

*  实现思路:

假设实现的目标函数为 `c()`, 由于目标是求 `[1,7]` 等概率返回一个, 如果我们能加工得到一个`b()`函数, 这个函数是等概率返回 `[0,6]` 范围内的任意一个数, 那么目标函数 `c()` 只需要调用这个 `b()` 函数再加上 `1`, 就可以等概率返回 `[1,7]` 中任意一个数, 即 `c()` 函数.

// 等概率返回 [1,7] 中任意一个数
    public static int c() {
        
        // b()函数是等概率返回 [0,6] 中的任意一个数
        // 在获取b()的基础上再加1就是等概率返回1~7了
        return b() + 1;
    }

接下来问题就变成了 `b()` 这个函数的实现, 要实现 `[0,6]` 等概率返回一个数, 思路如下:

先得到一个 0 和 1 等概率返回的随机函数 a(),

可以通过题目中给的 f() 函数来加工得到 a(),

f() 是 \[1,5\] 等概率返回的一个数, 也就是说, 调用 f() 会等概率返回 1,2,3,4,5 中的一个数, 我们约定,

当调用 f(), 得到 1 或者 2 的时候, 返回 0;

当调用 f(), 得到 4 或者 5 的时候, 返回 1;

当调用 f(), 得到 3 的时候, 什么都不返回, 再次调用 f().

代码如下:

// 利用[1,5]随机函数f() 生产等概率返回 0 和 1 的函数 a()
    public static int a() {
        
        // 约定拿到1和2就代表0, 拿到4和5就代表1
        // 拿到的是3就重新获取
        int answer = 0;
        do {
        
            answer = f();
        } while (answer == 3);
        return answer < 3 ? 0 : 1;
    }

这样就得到了 0 和 1 等概率返回的随机函数`a()`,

由于 `6` 的二进制表示是 `110`, 所以区间 `[0,6]` 的所有整数只需要 3 个二进制位就可以表示,

调用三次 `a()`函数, 就可以等概率得到 `[0,7]` 范围内任意一个数 (因为区间`[0,7]`用二进制表示就是 `000~111`)，即 `[0,1,2,3,4,5,6,7]` 等概率返回一个，

在得到 7 的时候, 重试上述过程, 只有结果在 `[0,6]` 才返回, 这样就加工出了 `b()` 函数, 即等概率返回 `[0,6]`.

// 再利用a()生产能等概率拿到0到6的函数
    public static int b() {
        
        // 三个二进制位就可以表示最大为6的数 (M N Y)
        int ans = 0;
        do {
              // 
            ans = (a() << 2) // 得到 M
            + (a() << 1) // 得到 N
            + a(); // 得到 Y
        } while (ans == 7);
        return ans;
    }

最后, 目标函数 `c()` 通过如下方式得到:

// 在获取b()的基础上再加1就是等概率返回1~7了
    public static int c() {
        
        return b() + 1;
    }

*  完整代码实现:

/**
     * 使用1~5的随机函数加工出1~7的随机函数
     */
    // 这个函数是等概率返回1~5的函数,只能使用,不能修改
    public static int f() {
        
        // (int)[0,5) -> [0,4] -> +1 -> [0,5]
        return (int)(Math.random() * 5) + 1;
    }
    // 利用[1,5]随机函数f() 生产等概率返回 0 和 1 的函数 a()
    public static int a() {
        
        // 约定拿到1和2就代表0, 拿到4和5就代表1
        // 拿到的是3就重新获取
        int answer = 0;
        do {
        
            answer = f();
        } while (answer == 3);
        return answer < 3 ? 0 : 1;
    }
    // 再利用a()生产能等概率拿到0到6的函数
    public static int b() {
        
        // 三个二进制位就可以表示最大为6的数 (M N Y)
        int ans = 0;
        do {
              //
            ans = (a() << 2) // 得到 M
                    + (a() << 1) // 得到 N
                    + a(); // 得到 Y
        } while (ans == 7);
        return ans;
    }
    // 在获取b()的基础上再加1就是等概率返回1~7了
    public static int c() {
        
        return b() + 1;
    }

*  测试代码:

测试 10000000 次, 每次记录随机生成的数字, 得到每个数字出现的次数

public static void main(String[] args) {
        
        // 测试次数
        int testTimes = 10000000;
        // random函数的测试
        int count = 0;
        int[] counts = new int[8];
        for (int i = 0; i < testTimes; i++) {
        
            int num = c();
            counts[num]++;
        }
        System.out.println(Arrays.toString(counts));
    }

*  执行结果:

![img][img 1]

可以看到 1 到 7 这些数字出现的次数都差不多, 接近等概率.

和问题一的思想一样, f() 函数是等概率函数, 那么将 f() 多次调用得到的结果一样是等概率的, 调用 7 次 f() 相加, 得到的结果 % 7以后, 最后得到的一定是等概率返回 0~6 中任意一个整数的, 再加1, 就变成等概率返回 1~7 任意一个.

public static int g2() {
        
    	return (f() + f() + f() + f() + f() + f() + f()) % 7 + 1;
    }

## 3. LeetCode 470. 用 Rand7() 实现 Rand10() ##

给定方法 `rand7` 可生成 `[1,7]` 范围内的均匀随机整数, 试写一个方法 `rand10` 生成 `[1,10]` 范围内的均匀随机整数; 你只能调用 `rand7()` 且不能调用其他方法, 请不要使用系统的 `Math.random()` 方法.

在线OJ: [LeetCode 470. 用 Rand7() 实现 Rand10()][LeetCode 470. _ Rand7_ _ Rand10]

*  实现思路:

思路上面基本一致, 核心都是**要先实现一个等概率返回 0 和 1 的随机函数** `f()`, 然后看目标函数区间需要几个二进制位, 来决定调用几次 `f()` 函数.

*  代码实现:

/**
     * The rand7() API is already defined in the parent class SolBase.
     * public int rand7();
     * @return a random integer in the range 1 to 7
     */
    class Solution extends SolBase {
        
        // 核心: 生成 0 和 1 等概率返回的随机函数
        public int f() {
        
            int val = rand7();
            while (val == 7) {
        
                val = rand7();
            }
            return (val <= 3) ? 0 : 1;
        }
    
        public int rand10() {
        
            int num = 0;
            do {
        
                num = 0;
                // 10 最多用4个二进制位表示即可
                for (int i = 0; i < 4; i++) {
        
                    num += (f() << i);
                }
            } while (num < 1 || num > 10);
            return num;
        }
    }

此外, 本题还有另外一种解法, 由 10 个 rand7() 之和得到的值 % 10 以后, 得到的一定是等概率返回 `[0,9]` 中的一个数, 再加 1, 就是等概率返回`[1,10]`了, 代码如下:

public int rand10() {
        
        return (rand7() + rand7() + rand7() + rand7() + rand7() + rand7() + 
                rand7() + rand7() + rand7() + rand7()) % 10 + 1;
    }

## 4. 把不等概率随机函数变成等概率随机函数 ##

有一个函数 `x()`, 不等概率 (但是是固定概率) 返回 0 和 1, 如何只通过 f() 函数, 得到等概率返回 0 和 1 的随机函数?

*  实现思路:

调用两次 `x()` 函数, 可以得到如下情况

情况1：0 0
    情况2：1 1
    情况3：0 1
    情况4：1 0

当两次都是 0, 或者两次都是 1 的时候, 即情况 1 和 情况 2, 就舍弃, 这样虽然 0 和 1 的概率不一样, 但是通过两次调用, 得到即情况 3 (0, 1)和 情况 4 (1, 0) 的概率一定是相同的, 所以我们可以约定,

所以, 我们可以约定, 两次调用得到的结果是 `0 1` 就返回 0, 得到的是 `1 0`就返回 1.

*  代码实现:

public class Code_0003_EqualProbabilityRandom {
        
    
        // 不等概率函数，
        // 内部内容不可见
        public static int f() {
        
            return Math.random() < 0.8 ? 0 : 1;
        }
    
        // 等概率返回0和1
        public static int g() {
        
            int first;
            do {
        
                first = f(); // 0 1
            } while (first == f());
            return first;
        }
    
    
        public static void main(String[] args) {
        
            final int testTimes = 10000000;
            // count[0] 统计0出现的次数
            // count[1] 统计1出现的次数
            int[] count = new int[2];
            for (int i = 0; i < testTimes; i++) {
        
                count[g()]++;
            }
            System.out.println("0 出现的次数:" + count[0]);
            System.out.println("1 出现的次数:" + count[1]);
        }
    }
    
    /**
     * 提供当0和1以不同的概率返回, 设计函数让0和1以等概率返回
     */
    public static int x() {
        
        return Math.random() < 0.66 ? 0 : 1;
    }
    
    // 等概率返回0和1
    public static int y() {
        
        // 两次获取01或者10就是等概率的
        // 两次获取到11或者是00就是不等概率的,舍弃
        int ans = 0;
        do {
        
            ans = x();
        } while (ans == x());
        return ans;
    }

*  测试代码:

调用 10000000 次, 记录 1 和 0 出现的次数.

public static void main(String[] args) {
        
        // 测试次数
        int testTimes = 10000000;
        int[] arr = new int[2];
        for (int i = 0; i < testTimes; i++) {
        
            int num = y();
            arr[num]++;
        }
        System.out.println(Arrays.toString(arr));
    }

测试结果:

![img][img 2]

可以看到 1 和 0 实际出现的次数差不多, 是接近等概率的.

## 5. 用a ~ b的随机函数加工出c ~ d的随机函数 ##

如何用一个生成区间 a ~ b 的随机函数加工生生产出成 c ~ d 的随机函数.

*  实现思路:

核心思路与前面的问题是一样的, 都是构造等概率生成 0 和 1 的 `rand()` 函数, 然后通过 `rand()`函数加工出随机生成 c ~ d 的函数.

假设生成区间 a ~ b 的随机函数是`f(a,b)`,

如果 a ~ b 的区间元素个数是`偶数`, 那么将区间分两半, 如果得到的是前面一半的数, 则返回 0; 如果得到后面一半的数, 则返回 1；

如果 a ~ b 的区间元素个数是`奇数`, 那么把将区间分两半, 如果得到的是前面一半的数, 则返回 0; 如果得到后面一半的数, 则返回 1; 得到中间位置的数, 则舍弃, 然后继续调用；

这样一来, 就加工出一个等概率随机生成 0 或 1 的函数 `rand()`, 然后就要判断要表示 1 ~ d - c + 1 这个范围的的值需要几个二进制(让 `1<<i - 1` 到大于范围即可), 不过由于这里的 c,d 并不是确定的值, 无法计算得到准确所需需要的二进制位数, 不过并不影响结果, 得到结果后判断结果是不是在范围内, 不在的话接着重新调用获取即可, 这样就可以得到随机生成 c ~ d 的函数了.

*  代码实现:

// 构造一个等概率返回a~b的随机函数
    public static int f(int a, int b) {
        
        // Math.random() -> [0, 1)
        // [a, b] -> a + [0,b-a] -> a + (int)(Math.random() * (b-a+1))
        return a + (int) (Math.random() * (b - a + 1));
    }
    
    // 要根据f()加工出等概率返回0和1的随机函数
    public static int rand(int a, int b) {
        
        // a = 4, b = 8
        // countNum = 5
        int countNum = b - a + 1; // 可能出现的随机数的个数
        // isOdd = true
        // 是否为奇数个
        boolean isOdd = countNum % 2 != 0;
        int midNum = (a + b) / 2;
        int ans;
        do {
        
            // 如果是奇数, 那么中点位置弃用, < 中点 位置 和 > 中点位置的数字返回概率一样, 一个定为0, 一个定为1
            // 如果是偶数, 那么这里的中点是上中点, < 上中点 位置 和 >= 上中点位置的数字出现的概率一样, 一个定为0, 一个定为1即可
            ans = f(a, b);
        } while (isOdd && ans == midNum);
    
        // 如果是偶数，ans可能会等于midNum
        // 如果是奇数，ans必不等于midNum
        return ans <= midNum ? 0 : 1;
    }
    
    // 加工出等概率返回c~d的随机函数
    public static int g(int a, int b, int c, int d) {
        
        int range = d - c; // 0～range + c~d -> c~d
        int count = 1;
    
        while ((1 << count) - 1 < range) {
         // 求0～range需要几个2进制位
            count++;
        }
        int ans;
        do {
        
            ans = 0;
            for (int i = 0; i < count; i++) {
        
                ans += (rand(a, b) << i);
            }
            // 要注意这里的实现, 由于这里 c,d 是随机给出的, 也就不好准确计算出所需要的进制位
            // 所以, 要判断最终的结果是不是在范围内, 不在的话要重新调用获取
        } while (ans > range);
        return ans + c;
    }

*  测试代码:

public static void main(String[] args) {
        
        // 测试次数
        int testTimes = 10000000;
        int[] array = new int[20];
        for (int i = 0; i < testTimes; i++) {
        
            int num = g(3, 19, 20, 39);
            array[num-20]++;
        }
        System.out.println(Arrays.toString(array));
    }

*  测试结果:

![img][img 3]

可以看到每个数实际出现的次数是差不多的, 接近等概率.

[img]: https://img-blog.csdnimg.cn/img_convert/3f86cc7d0974442bec05ef52ec254daa.png
[img 1]: https://img-blog.csdnimg.cn/img_convert/966c5ddd7d8bcdfdbb033a6090f906e3.png
[LeetCode 470. _ Rand7_ _ Rand10]: https://leetcode.cn/problems/implement-rand10-using-rand7/
[img 2]: https://img-blog.csdnimg.cn/img_convert/7fe33d4ea46f12b0b4fc22438d3eab22.png
[img 3]: https://img-blog.csdnimg.cn/img_convert/fc920225de8010796925baa3e93ba30b.png