如何逐个生成大量唯一乱序数字并快速恢复生成状态？

核心思路 #

要解决100亿级别的唯一随机数生成问题，无需一次性生成并存储所有数字，可采用伪随机排列生成器——这类算法能遍历目标范围的一个随机排列，逐个输出元素，仅需存储少量状态，还能快速定位到任意生成步骤。

常用算法实现 #

1. 全周期线性同余生成器（LCG） #

这是最经典且易实现的方案，通过选择符合Hull-Dobell定理的参数，让生成序列覆盖目标范围的全排列（每个数仅出现一次）。

全周期参数要求

• 增量c与模数m互质
• 乘数a-1能被m的所有质因数整除
• 若m是4的倍数，a-1也必须是4的倍数

实践参数（适配64位范围）

对于m=2^64（完全覆盖100亿的需求），可使用经过验证的稳定参数：

• a=6364136223846793005
• c=1442695040888963407

Python实现示例

class FullCycleLCG:
    def __init__(self, seed=1, target_range=10**10):
        self.m = 2**64
        self.a = 6364136223846793005
        self.c = 1442695040888963407
        self.target_range = target_range
        self.current = seed % self.m
        self.seed = seed

    def next(self):
        while True:
            self.current = (self.a * self.current + self.c) % self.m
            num = self.current % self.target_range + 1  # 转换为1~target_range的范围
            if num <= self.target_range:
                return num

    def jump_to_step(self, k):
        # 快速计算k次迭代后的状态
        a_pow = pow(self.a, k, self.m)
        # 计算c*(a^k - 1)/(a-1) mod m，因a-1是2的幂，除法等价于右移
        c_term = self.c * ((a_pow - 1) // (self.a - 1)) % self.m
        self.current = (a_pow * self.seed + c_term) % self.m

特性

• 内存占用：仅需存储几个整数（约8字节核心状态）
• 状态恢复：通过快速幂计算直接跳转到第k步，时间复杂度O(log k)
• 唯一性：全周期参数保证每个数仅出现一次，直到遍历完整个范围

2. 质数模数下的原根生成器 #

如果目标范围的上限是质数p，可利用原根特性生成全排列：

• 选择质数p的一个原根g，序列x_k = g^k mod p会遍历1~p-1的所有数，0可单独处理
• 状态仅需存储当前指数k或当前值x_k，跳转到第k步直接计算pow(g, k, p)即可

3. 密码学安全方案：AES-CTR模式 #

若需要抗攻击的安全性，可使用AES的CTR模式：

• 将计数器作为输入，每次加密计数器值得到唯一的随机数
• 状态仅需存储当前计数器值，跳转到第k步只需将计数器设为k
• 保证绝对的唯一性和密码学安全性，适合敏感场景

关键注意点 #

• 非2的幂范围处理：若目标范围不是2的幂（如100亿），可使用拒绝采样——生成的数若超出范围则丢弃，直到得到符合要求的数。因100亿远小于2^64，拒绝概率极低，性能影响可忽略
• 性能选择：LCG实现最简单，性能足够；Xorshift128+或AES-CTR性能更高，适合超大规模生成

内容的提问来源于stack exchange，提问作者g00dds