收录一些离散随机数生成的问题。

1. 洗牌

先从最简单的开始。

随机生成一个全排列，那必然是著名的洗牌算法。

#include <bits/stdc++.h>

std::vector<int> shuffle(int n) {
    std::vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        arr[i] = i;
    }
    for (int i = n - 1; i > 0; i--) {
        std::swap(arr[i], arr[rand() % (i + 1)]);
    }
    return arr;
}

int main() {
    std::vector<int> a = shuffle(10);
    for (auto i : a) {
        printf("%d ", i);
    }
    return 0;
}

2. 随机数转换

有一个骰子可以掷出范围 $[0, A - 1]$ 的随机数，如何生成范围 $[0, B - 1]$ 的随机数。

假设 $A = 10, B = 7$，我们可以不断掷骰子直到出现范围 $[0, 6]$ 的数字，但是投出 7, 8, 9，它们的信息也不要浪费。因此就有下面这个算法。

#include <bits/stdc++.h>

int randAToB(int A, int B, const std::function<int()> &randA) {
    int x = 0;
    int sz = 1;
    while (x / B == sz / B) {
        x %= B;
        sz %= B;
        x = x * A + randA();
        sz *= A;
    }
    return x % B;
}

int randA() { return rand() % 2; }

int main() {
    for (int i = 0; i < 20; i++) {
        printf("%d\n", randAToB(10, 7, randA));
    }
    return 0;
}

在这个问题中，如果存在一个数是 B 的质因子但不是 A 的质因子，很显然我们必须用试错法。（我称这个定理为试错法基本定理）

这里的试错法是指，通过反复尝试，直到成功。

缺点就是，如果 randA 函数可以被黑客操控，我们的这个循环可能变成死循环。

3. 随机大数

给定一个大数 N，生成 $[0, N-1]$ 范围里的随机数。为了方便，大数就按 10 进制，一位一位存入 std::vector<int> 里，输入输出都是如此。

根据试错法基本定理，很显然这题也是必须试错的。

既然已经确定要试错了，那么失误率越小越好。这里的思路是将最大 4 位合成整数 t，然后生成 $[0,t]$，剩下的每一位都随机生成 $[0,9]$，然后判断生成的数是否小于 N。

很显然，最大 4 位数一定大于等于 1000，那么在 $[0,t]$ 里生成的随机数小于 t 是非常有可能的（概率不低于 99.9%），这样失误率（千分之一）就降到很低了。

如果千分之一还不满意，可以把最大 4 位数改成 9 位。

#include <bits/stdc++.h>

std::vector<int> randBigInt(std::vector<int> N) {
    int pos = std::max(0, (int)N.size() - 4);
    std::vector<int> res(N.size(), 0);
    int t = 0;
    for (int i = (int)N.size() - 1; i >= pos; i--) {
        t = t * 10 + N[i];
    }

    while (true) {
        int h4 = rand() % (t + 1);
        for (int i = pos; i < (int)N.size(); i++) {
            res[i] = h4 % 10;
            h4 /= 10;
        }
        for (int i = 0; i < pos; i++) {
            res[i] = rand() % 10;
        }
        for (int i = (int)N.size() - 1; i >= 0; i--) {
            if (res[i] < N[i]) {  // res < N
                while (res.size() >= 2 && res.back() == 0) {
                    res.pop_back();
                }
                return res;
            }
            if (res[i] > N[i]) {  // res > N
                break;
            }
        }
    }
}

int main() {
    std::vector<int> N = {1, 2, 3, 4, 5}; // N = 54321
    for (int i = 0; i < 20; i++) {
        std::vector<int> res = randBigInt(N);
        for (int j = (int)res.size() - 1; j >= 0; j--) {
            printf("%d", res[j]);
        }
        puts("");
    }
    return 0;
}