咨询无需存储生成指定范围唯一随机数的可行算法

当然存在这类无需额外存储空间的算法，核心是利用数学上的置换特性或概率抽样，避免存储已生成的数：

1. 线性置换生成法（通用场景） #

不管m和n的大小关系，都可以用这种方法直接生成不重复的随机数，全程只需要存储两个随机参数，不需要记录已生成的数：

• 原理：当整数a与n互质时，函数f(i) = (a*i + b) mod n是0到n-1的一个全排列（双射），因此取前m个不同的i（比如0到m-1），得到的结果必然唯一。
• 实现步骤：
  1. 随机选一个与n互质的整数a（1 ≤ a < n）
  2. 随机选一个偏移量b（0 ≤ b < n）
  3. 对每个i从0到m-1，计算(a*i + b) % n，得到的就是m个唯一随机数

Kotlin实现代码：

import kotlin.random.Random
import kotlin.math.gcd

fun generateUniqueRandoms(m: Int, n: Int): List<Int> {
    // 生成与n互质的a
    var a = Random.nextInt(1, n)
    while (gcd(a, n) != 1) {
        a = Random.nextInt(1, n)
    }
    val b = Random.nextInt(n)
    return (0 until m).map { (a * it + b) % n }
}

// 调用示例
val m = 100
val n = 1_000_000_000
val uniqueRandoms = generateUniqueRandoms(m, n)

2. 概率拒绝采样法（m远小于n场景） #

当m远小于n时（比如m=100，n=1e9），用这种方法更简单，只需记录当前已生成的数量，无需存储已选数：

• 原理：基于蓄水池抽样的思想，每个数被选中的概率均等，通过动态调整保留概率避免重复。
• 实现步骤：
  1. 初始化计数器k=0（记录已生成的有效数数量）
  2. 循环生成随机数v，计算保留概率(m - k)/(n - k)，若随机数落在该概率范围内则保留，k加1
  3. 直到k达到m为止

Kotlin实现代码：

import kotlin.random.Random

fun generateUniqueRandoms(m: Int, n: Int): List<Int> {
    val result = mutableListOf<Int>()
    var k = 0
    while (k < m) {
        val v = Random.nextInt(n)
        // 用乘法避免浮点精度问题：(m - k) * 随机数最大值 >= (n - k) * 随机值
        if (Random.nextLong(n - k) < (m - k).toLong()) {
            result.add(v)
            k++
        }
    }
    return result
}

关键优势 #

• 两种方法都不需要存储所有已生成的数，内存开销仅为常数级别，完全适配十亿级别的n或m
• 每次执行时通过随机选择参数或随机概率判断，保证结果不重复

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