【算法专题】Rand 概率生成

2024-01-03 2024-08-26 约 3100 字预计阅读 7 分钟

部分内容转自 Images’ Blog：【LeetCode】430. Rand7 实现 Rand10

抛硬币（Rand2）

不均匀硬币产生均匀概率分布

现有一枚不均匀的硬币 coin()，能够返回 0、1 两个值，其概率分别为 0.6、0.4。要求使用这枚硬币，产生均匀的概率分布。即编写一个函数 coin_new() 使得它返回 0、1 的概率均为 0.5。

1
2
3
4


// 不均匀硬币，返回 0、1 的概率分别为 0.6、0.4
int coin() {
    return (rand() % 10) > 5;
}

统计抛两次硬币的结果的概率分布：

结果	0	1
0	0.6*0.6=0.36	0.6*0.4=0.24
1	0.4*0.6=0.24	0.4*0.4=0.16

不难发现，连续抛两枚硬币得到 0 1 和 1 0 的概率分布是相同的。因此这道题的解法就是连续抛两次硬币，如果得到 0 1，返回 0；如果得到 1 0，返回 1；如果两次结果相同，则重新抛。

以此类推，无论这枚不均匀硬币的概率是多少，都可以用这种方法得到等概率的结果。

1
2
3
4
5
6


int coin_new() {
    while (true) {
        int a = coin();
        if (coin() != a) return a;
    }
}

完整测试代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


#include <iostream>
#include <map>
using namespace std;

// 不均匀硬币
int coin() {
    return (rand() % 10) > 5;
}

int coin_new() {
    while (true) {
        int a = coin();
        if (coin() != a) return a;
    }
}

// 测试
int main() {
    int N = 1000000;
    float count[2] = {0, 0};
    for (int i = 0; i < N; i++)
        count[coin_new()] ++;

    cout << "0: " << count[0]/N << endl;
    cout << "1: " << count[1]/N << endl;
}

均匀硬币产生不均匀概率分布

现有一枚均匀的硬币 coin()，能够返回 0、1 两个值，其概率均为 0.5。要求编写一个函数 coin_new()，使得它返回指定的 0、1 概率分布。

1
2
3
4


// 均匀硬币
int coin() {
    return rand() % 2;
}

要得到 $P(0) = 1/4，P(1) = 3/4$（00->0，01/10/11->1）

1
2
3


int coin_new() {
    return coin() || coin();
}

要得到 $P(0) = 1/3，P(1) = 2/3$（11->0，01/10->1，00->重新投）

1
2
3
4
5
6
7


int coin_new() {
    while (true) {
        int a = coin(), b = coin();
        if (a && b) return 0;
        if (a || b) return 1;
    }
}

要得到 $P(0) = 0.3，P(1) = 0.7$

每抛一次硬币，会得到二进制数的一位
连续抛 4 次硬币，可以等概率生成 [0, 15] 的每个数，记为 x
去掉 [10, 15]，剩下 [0, 9] 的每个数依然是等概率的
如果 x∈[0,2]，返回 0；x∈[3,9]，返回 1；x≥10，重复上述过程

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


int coin_new() {
    while (true) {
        int x = 0;
        for (int i = 0; i < 4; i++) {
            int x = (x << 1) + coin();
        }
        if (x <= 2) return 0;
        if (x <= 9) return 1;
    }
}

总结一下：不难发现，上面这三道题目其实都是同一种思路

每抛一次硬币，会得到二进制数的一位
连续抛 k 次硬币，可以等概率生成 $[0, 2^k − 1]$ 的每个数
在 $[0, 2^k − 1]$ 中，选取 m 个数返回 0，n 个数返回 1，则 0、1 的概率分别为 $\frac{m}{m+n}$、$\frac{n}{m+n}$

关于 k 的选择，最少需要满足 $N<=2^k−1$，N 是生成对应概率分布至少需要多少个不同数字。

比如要生成 1/3、2/3 的分布，至少需要 3 个不同数字，即 N=3, k=2；要生成 3/10、7/10 的分布，至少需要 10 个数字，即 N=10, k=4。

k 没有上限，我们总可以通过抛更多次硬币来解决问题，只需要把无用的数字舍弃即可。但我们的目的是尽可能减少无用数字的比例，因为每次遇到无用数字时，都需要重新生成新的数字。

RandM 实现 RandN

Rand5 实现 Rand3

rand5 -> $[1,5]$，rand3 -> $[1, 3]$，不在 rand3 范围内的重新生成即可。

1
2
3
4
5
6


int rand3() {
    while (true) {
        int x = rand5();
        if (x <= 3) return x;
    }
}

Rand7 实现 Rand10

leetcode-470. 用 Rand7() 实现 Rand10() | Code

已有方法 Rand7() 可生成 1 到 7 范围内的均匀随机整数，试写一个方法 Rand10() 生成 1 到 10 范围内的均匀随机整数。

抛硬币可以看作是 Rand2()，先考虑 Rand2() 生成 Rand10()

1
2
3
4
5
6
7
8
9


int rand10() {
    while (true) {
        int x = 0;
        for (int i = 0; i < 4; i++) {
            x = (x << 1) + rand2();
        }
        if (1 <= x && x <= 10) return x;
    }
}

回到这道题，我们可以将 Rand7() 视作一个 7 进制位的生成器。由于 Rand7() 的结果范围是 [1, 7]，故我们取 Rand7() - 1 作为对应的 7 进制位。每执行 k 次 Rand7()，将得到一个 k 位的 7 进制整数，在 $[0,7^k−1]$ 范围内均匀分布。

对于本题而言，只需执行 k=2 次 Rand7()，就可以得到范围为 [0,48] 的均匀整数：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


class Solution {
public:
    int rand10() {
        while (true) {
            // int x = 0;
            // for (int i = 0; i < 2; i++) {
            //     x = x * 7 + rand7() - 1;
            // }
            int x = (rand7() - 1) * 7 + (rand7() - 1);
            if (x >= 1 && x <= 10) return x;
        }
    }
};

写法二，更规整的代码：$[0,7^k−1] + 1$ -> $[1,7^k]$

1
2
3
4
5
6
7
8
9


class Solution {
public:
    int rand10() {
        while (true) {
            int x = (rand7() - 1) * 7 + rand7();  // [1, 49]
            if (x <= 10) return x;
        }
    }
};

优化：减少舍弃的数字，一共 $[1,49]$ 从利用 $[1,10]$ 到利用 $[1,40]$，只剩 $41,42…,49$ 一共9个无用数字

1
2
3
4
5
6
7
8
9


class Solution {
public:
    int rand10() {
        while (true) {
            int x = (rand7() - 1) * 7 + rand7();  // [1, 49]
            if (x <= 40) return x % 10 + 1;
        }
    }
};

进一步优化：对于上面这 9 个无用数字，计算 $x - 40$ 可以得到 $[1, 9]$ 范围的均匀随机整数。此时再调用一次 Rand7()，计算 $ (x - 41) * 7 + Rand7()$，这相当于 $ (Rand9() - 1) * 7 + Rand7()$。

当使用 $[0,7^k−1] + 1$ 表示时，多余数字为 $0,41,42…,48$，可计算 x % 40 可以得到 $[0, 8]$ 范围的均匀随机整数

显然，我们可以得到 $[1, 63]$ 范围的均匀随机整数。这时 $[1, 60]$ 范围里的数都可以用来作取余运算，只有 $61,62,63$ 共 3 个无用数字。

对于 61、62、63，我们也可以用相同的思路，再调用一次 Rand7()，计算 $(x - 61) * 7 + Rand7()$，相当于 $ (Rand3() - 1) * 7 + Rand7() $。

可以得到 $[1, 21]$ 范围的均匀随机整数，这时再作取余运算，只有 1 个无用数字（21）：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21


class Solution {
public:
    int rand10() {
        while (true) {
            int x = (rand7() - 1) * 7 + rand7();    // [1, 49]
            if (x <= 40) return x % 10 + 1;         // [1, 40]

            // x = 41, 42, ..., 49
            int a = x - 40;                     // rand9()
            x = (a - 1) * 7 + rand7();          // rand63()
            if (x <= 60) return x % 10 + 1;     // [1, 60]

            // x = 61, 62, 63
            a = x - 60;                         // rand3()
            x = (a - 1) * 7 + rand7();          // rand21() [1, 21]
            if (x <= 20) return x % 10 + 1;     // [1, 20]

            // x = 21 (next loop)
        }
    }
};

注意每次乘的系数都是 7，被乘数也要从 0 开始，可以理解为 7 进制条件

这是为了保证等概率：当乘的系数大于 7 或者小于 7，都无法保证等概率

rand5 生成 rand7

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


int rand7() {
    while (true) {
        int x = (rand5() - 1) * 5 + rand5();    // [1, 25]
        // if (x <= 7) return x;
        if (x <= 21) return x % 7 + 1;          // [1, 21]

        // x = 22 23 24 25
        int a = x - 21; // rand4()
        x = (a - 1) * 5 + rand5();              // [1, 20]
        if (x <= 14) return x % 7 + 1;          // [1, 14]

        // x = 15,16,...,20
        //...
    }
}

通用方法

RandM 生成 RandN

已知 $RandM()$ 可以等概率的生成 $[0, M-1]$ 范围的随机整数，那么执行 $k$ 次，每次都得到 $M$ 进制的一位，可以等概率生成 $[0,M^k−1]$ 范围的随机整数，记为 $x$
RandN 至少需要 $N$ 个均匀随机整数，因此只需要取 $k$，使得 $M^k−1>=N$ 即可
此时有多种方式得到 RandN：
- 简单：只在 $x∈[0,N−1]$ 时返回 $x$
- 多层：利用取余运算，在保证等概率的前提下，尽可能多的利用生成的数字，从而减少舍弃的数字比例，降低 while 重复执行的概率

案例-员工公平抽奖

例1：现有 30w 员工抽奖，抽 1000 个，有一个 rand 函数生成 0-65535 之间的任意随机数，保证每个员工获奖概率相同如何实现。

思路一：30w 员工按 6w (< 65535) 分组，分成 5 组，rand65535 实现 rand60000
思路二：rand65535 实现 rand300000（生成 0-300000 之间的任意随机数）

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


int rand300000(){
    while (true) {
        // rand65536(): [0, 65535]
        int x = rand65535() * 65536 + rand65535();  // rand65536^2(): [0, 65536^2 - 1]
        // 65536 * 65536 = 4,294,967,296
        // 4,294,967,296 / 300000 = 14316 ... 167,296
        // if (x >= 1 && x <= 14316 * 300000) return x % 300000;    // [1, 14316 * 300000] -> [0, 300000]
        if (x < 14316 * 300000) return x % 300000;      // [0, 14316 * 300000 - 1] -> [0, 300000]

        // x = [14316 * 300000 - 1, 65536 * 65536 - 1]
        // todo: 进一步深层优化
    }
}

// 洗牌算法
set<int> solution(int targetNum){
	set<int> result;
	while (result.size() != targetNum) {
	    int selectNum = rand300000();
	    while (result.find(selectNum) != result.end()){
		    selectNum = rand300000();
		}
		result.insert(selectNum);
	}
}

例2：有 30w 员工，现在要均匀抽出 1w 员工发奖品，提供一个随机数生成器函数 rand16() 随意调用，请写一个函数 selectLuckyStaffs() 实现这个功能。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


int rand300000(){
    while (true) {
        // 16^4 = 65536, 16^5=1,048,576
        int x = 0;
        for (int i = 0; i < 5; i++) {
            x = x * 16 + rand16();
        }
        // int x = rand16() * 65536 + rand16() * 4096 + rand16() * 256 + rand16() * 16 + rand16();
        // 16^5=1,048,576 / 300000 = 3
        if (x < 3 * 300000) return x % 300000;

        // ...
    }
}

// 洗牌算法
// ...

Reference

【LeetCode】430. Rand7 实现 Rand10

收录于合集・算法笔记 14

【算法专题】快慢指针的应用【算法专题】海量数据处理