如何在O(log(n))空间复杂度下生成不含重复的n个随机数序列

方案1：基于l-wise哈希的比较排序实现 #

该方案无需存储任何元素使用标记，仅需要O(log n)的额外空间：

• 选取2-wise独立的均匀哈希函数h: [n] -> [n²]，哈希本身仅需要存储随机生成的种子，空间开销为O(log n)，无需存储映射表
• 定义两个不同整数i,j ∈ [1,n]的比较规则：若h(i) < h(j)则i排在j前，反之j排在i前
• 采用空间复杂度为O(log n)的原地排序算法（如原地快速排序、堆排序），对1~n的整数序列按上述规则排序，得到的结果即为符合要求的均匀随机排列

原理：2-wise独立哈希可以保证任意两个不同元素的哈希值大小关系完全随机，最终排序得到的排列和均匀随机排列的统计特性一致，全程无O(n)级别的额外空间开销，时间复杂度为O(n log n)。

方案2：全周期线性同余生成器(LCG)实现 #

该方案时间复杂度为O(n)，仅需要3个整数的存储空间，完全符合空间要求：

• 递推公式调整为x_i = (a * x_{i-1} + c) mod n，最终输出结果加1即可得到[1,n]区间的整数
• 只要参数满足以下三个充要条件，即可保证生成序列的周期为n，天然无重复：
  • 增量c和n互质，即gcd(c,n) = 1
  • a-1可以被n的所有质因数整除
  • 若n是4的倍数，则a-1也必须是4的倍数
• 你只需要对n做质因数分解即可快速构造符合要求的a、c参数，质因数分解的空间开销也为O(log n)，无需额外存储已使用元素。

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