用rand5()生成rand7()随机数

rejection sampling：用两个rand5()调用5*rand5()+rand5()生成[0..24]的平均分布，使用其中的[0..20]，抛掉多余的范围

int rand7() {
    while (true) {
        int num = 5 * rand5() + rand5();
        if (num < 21) return num % 7;
    }
}

n个数中选k个

记录还要选几个select、还剩几个可选remaining，每个数以p = 还要选几个/还剩几个可选的概率选中

vector<int> ans;
int select = k, remaining = n;
for (int i = 0; i < n; i++) {
    if (rand() % remaining < select) {
        ans.push_back(i);
        select--;
    }
    remaining--;
}
return ans;

从未知流中选k个值

水库抽样：先选中前k个数，然后生成[0,当前总数count)范围内的随机数r，当r<k时将ans[r]换成当前数，即当前数以p = 要选的个数/当前总数的概率选中

vector<int> ans;
int count = 0;
for (int num : inputstream) {
    count++;
    if (count <= k) {
        ans.push_back(num);
    } else {
        int r = rand() % count;
        if (r < k) ans[r] = num;
    }
}
return ans;
从未知流中选1个值

水库抽样的特例，以 1/当前总数 的概率替换旧选

class Solution {
    vector<int> nums;
public:
    Solution(vector<int> nums) : nums(nums) {
        srand(time(NULL));
    }

    int pick(int target) {        
        int ans = -1;
        int count = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] != target) continue;
            count++;
            // 以1/count概率替换旧选
            if (rand() % count == 0) ans = i;
        }
        return ans;
    }
};

带权重抽样

class Solution {
    vector<int> wsum;
public:
    Solution(vector<int> w) {
        partial_sum(begin(w), end(w), back_inserter(wsum));
        srand(time(NULL));
    }
    
    int pickIndex() {
        // 按概率选中某项 <=> 从左往右按累计概率选中某项（从左往右保证了排除掉前面的累计概率，只剩当前项的概率）
        int rnd = rand() % wsum.back();
        // 要rnd<wsum[i]，在wsum中找第一个>rnd的位置
        return upper_bound(begin(wsum), end(wsum), rnd) - begin(wsum);
    }
};

下标重映射

数组中有些元素不能选
class Solution {
    unordered_map<int, int> mapping; // 下标重映射
    int M;
public:
    Solution(int N, vector<int> blacklist) {
        unordered_set<int> st;
        for (int b : blacklist) {
            st.insert(b);
        }
        M = N - st.size();
        // N个数中只能选M个，将idx<M的不可选的数 =映射到=> idx>=M的可选的数
        for (int b : blacklist) {
            if (b < M) { 
                while (st.count(N - 1)) N--;
                mapping[b] = N - 1;
                N--;
            } 
        }
        
        srand(time(NULL));
    }
    
    int pick() {
        int idx = rand() % M;
        return mapping.count(idx) ? mapping[idx] : idx;
    }
};
已选中的元素不能再选
class Solution {
    // 把2D矩阵当作1D数组处理
    // Fisher-Yates洗牌：生成[0,n-1]随机数r，交换r和n-1，n--
    unordered_map<int, int> mapping; // 记录r和n-1的交换操作
    int rows, cols, n;
public:
    Solution(int n_rows, int n_cols) {
        rows = n_rows;
        cols = n_cols;
        n = rows * cols;
        srand(time(NULL));
    }
    
    vector<int> flip() {
        int r = rand() % n;
        // 交换r和n-1索引在mapping中的值
        int tmp = getMapping(r);
        mapping[r] = getMapping(n-1);
        mapping[n-1] = tmp;
        n--;
        return { tmp / cols, tmp % cols };
    }
    
    int getMapping(int idx) {
        return mapping.count(idx) ? mapping[idx] : idx;
    }
    
    void reset() {
        mapping.clear();
        n = rows * cols;
    }
};