数学——概率统计--随机数生成¶

数学——概率统计--随机数生成¶

随机数生成器¶

C++生成随机数需要rand()和srand()。

两者的区别在于，rand()函数每次的随机数种子是相同的，生成的是0-INT_MAX之间的整数，是一种伪随机。srand()一般的用法是srand(time(NULL))，用系统时间初始化随机数种子，这样每次生成的序列是不同的。

#include <bits/stdc++.h>

using namespace std;

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    for (int i = 0; i < 10; ++i) {
        cout << (rand() % 100) << ' ';
    }
    cout << endl;

    return 0;
}

上面没有初始化随机数种子，每次生成的序列都是

83 86 77 15 93 35 86 92 49 21

，如果使用srand()：

#include <bits/stdc++.h>

using namespace std;

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    srand(time(NULL));

    for (int i = 0; i < 10; ++i) {
        cout << (rand() % 100) << ' ';
    }
    cout << endl;

    return 0;
}

85 58 84 46 3 34 71 17 18 49 
69 23 38 58 67 85 81 74 63 90 
95 0 45 28 80 24 82 64 52 28

会发现每次生成的序列都是不一样的。

常用规律总结：

随机生成[0, n)之间的整数：rand() % n
随即生成[a, b)之间的整数（a < b）：rand() % (b - a) + a
随机生成[a, b]之间的整数（ $a \leq b$ ）：rand() % (b - a + 1) + a
随机生成(a, b]之间的整数（a < b）：rand() % (b - a) + a + 1
取得[0,1]之间的浮点数：rand() * 1.0 / INT_MAX

非等概率随机数生成器转换成等概率随机数生成器¶

一类很经典的问题：一个随机数生成器以概率p生成0，以概率1-p生成1，如何让随机数生成器等概率的生成0和1？

两个相同的随机数生成器满足上述条件，记为f, g，那么f生成0并且g生成1的概率是p(1-p)，f生成1并且g生成0的概率是p(1-p)。这样就可以等概率的生成0和1，用一个while循环只有上述两种情况的时候输出。

不过存在的问题是假如p很小，那么生成0的概率是很小的，也就意味着可能要循环多次才会出现想要的结果。

将问题一般化：如果以概率 $p_1$ 生成0，概率 $p_2$ 生成1， $\cdots$ ，以概率 $p_n$ 生成n-1，如何等概率的生成0-n-1？其中 $\sum_{i=1}^n p_i = 1$ 。

等概率随机数生成器转成非等概率随机数生成器¶

如果一个随机数生成器等概率的生成0和1，如何让随机数生成器以概率p生成0，以概率1-p生成1，相当于上面问题的逆问题。

可以假定概率p以浮点数表示，精度为2位，比如p = 0.23，那么1 - p = 0.77，可以用随机数生成器等概率的生成0-99共100个数，其中0-22就输出0，23-99就输出1。如果精度是3或4等，就乘以相应的 $10^n$ 。

#include <bits/stdc++.h>

using namespace std;

int randomPick(int p)
{
    return rand() % 100 < p ? 0 : 1; 
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    double p; cin >> p;

    int prob = p * 100;
    cout << randomPick(prob) << endl;

    return 0;
}

问题拓展，如何以概率 $p_1, p_2, \cdots ,p_n$ 生成0到n-1，其中 $\sum_{i=1}^n p_i = 1$ 。

根据权重生成随机数¶

LeetCode 528.Random Pick with Weight

给定一个正整数数组 w ，其中 w[i] 代表位置 i 的权重，请写一个函数 pickIndex ，它可以随机地获取位置 i，选取位置 i 的概率与 w[i] 成正比。

题意是给定一个权重数组，根据权重占整体的比例（记为p），通过函数pickIndex以概率p返回其对应的下标。描述很拗口，就以第二个样例作为例子：

给定权重数组1,3，其中1占整体的比例为1/4，3占整体的比例为3/4，那么函数pickIndex应该以1/4的概率返回0（对应1的下标），以3/4的概率返回下标1。

不妨设权重总和为total，那么我们生成0-total - 1之间的整数，实际上就可以根据权重来对数字进行划分：

0 | 1 2 3

随机数生成器等概率的生成0-3之间的数字，那么假如生成的数字为0，就返回下标0，生成1或2或3，就返回下标1，这样就满足根据权重返回下标了。

为了确定数字和下标对应的关系，我们需要计算前缀和：

前缀和下标: 0 1 2
前缀和数据: 0 1 4

实际上确定对应关系就是根据前缀和数据查找第一个大于数字的值，用其在前缀和的下标然后减一。比如生成数字2，查找到的位置是4对应的下标2，pickIndex就返回2-1，查找过程很容易就联想到利用二分法。

class Solution {
    vector<int> preSum;
    int n;
public:
    Solution(vector<int>& w) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        n = w.size();
        preSum.resize(n + 1, 0);
        for (int i = 1; i <= n; ++i) {
            preSum[i] = preSum[i - 1] + w[i - 1];
        }
    }

    int pickIndex() {
        //srand(time(NULL));
        int total = preSum[n];
        int target = rand() % total;
        int res = upper_bound(preSum.begin() + 1, preSum.end(), target) - preSum.begin();

        return res - 1;
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(w);
 * int param_1 = obj->pickIndex();
 */

随机数索引¶

LeetCode 398.Random Pick Index

给定一个可能含有重复元素的整数数组，要求随机输出给定的数字的索引。您可以假设给定的数字一定存在于数组中。

注意：数组大小可能非常大。使用太多额外空间的解决方案将不会通过测试。

利用一个unordered_map<int, vector<int>> um存储每个数值对应的下标，那么随机返回一个索引，其实就是生成一个0-um[target].size() - 1的一个随机数，这样如果存在多次pick，那么每次都是 $O(1)$ 的效率。

class Solution {
    vector<int> preSum;
    int n;
public:
    Solution(vector<int>& w) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        n = w.size();
        preSum.resize(n + 1, 0);
        for (int i = 1; i <= n; ++i) {
            preSum[i] = preSum[i - 1] + w[i - 1];
        }
    }

    int pickIndex() {
        //srand(time(NULL));
        int total = preSum[n];
        int target = rand() % total;
        int res = upper_bound(preSum.begin() + 1, preSum.end(), target) - preSum.begin();

        return res - 1;
    }
};

/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(w);
 * int param_1 = obj->pickIndex();
 */