生成一个没有重复的n个随机数的序列，其空间复杂度为O(log(n))

Question

我想在区间[1,n]中生成一个没有重复的n随机整数序列，即具有O(log(n))空间复杂度的序列[1,2,...,n]的置换(或log(n)的多项式函数(。

一个提示是，我可以假设我有一个l-wise统一散列函数族h : [n] -> [k](具有l<=n(，使得对于任何y_1, y_2,..., y_l和任何不同的x_1, x_2,..., x_l:

P(h(x_1) = y_1 and h(x_2) = y_2 and ... and h(x_l) = y_l) = 1/(k^l)

我的第一个想法是使用哈希函数生成序列的第i个元素，即x_i = h(i)，检查是否已经使用了x_i(已经由某些0<j<i的哈希函数返回(，如果是这种情况，则将x_i增加1，然后再次检查，直到x_i是一个新数字。我的问题是，我不能使用大小为n的布尔值向量来检查值x_i是否已经使用。如果我做一个递归函数来得到第j个值，在某个点上我需要O(n log2(n))位。。。

我在这里还发现，像线性同余生成器这样的伪随机生成器可以用于像x_i+1 = (a*x_i + c)%n + 1这样的问题，但我不确定如何为n的任何值选择a以具有长度为n的周期。在这种情况下，除了生成序列的第一个数字之外，提示实际上并不有用，因此我认为这不是正确的方法。

Answer 1

这里有一个有趣的超简单的常量空间解决方案；当N是2的幂时；"随机"；非常松散(生成的序列将在偶数和奇数之间交替(。

N = power of 2
P = prime number larger than N.
S = random starting number between 0 and N-1
For i = 1 TO N
// add our prime to the starting random number
S += P
// S Modulus N
// Bitwise And N-1 works because N is a pow of 2
T = S & (N - 1)
//T is [0, (N-1)] => we want [1, N]
PRINT (T + 1) 
Next I

JS-

for(let N = 64, P = 73, S = N * Math.random(), i = 1; i <= N; i++) { S += P; console.log((S & (N - 1)) + 1); }

另一个答案可能是将所有的数字[1，N]视为树中的叶节点，而Log(N(空间是通过树的路径的大小。你的解决方案将是一个函数，通过树排列所有N条路径。以伪随机方式排列路径的方式基本上是线性反馈移位寄存器类型的生成器，它的周期比N大。https://www.maximintegrated.com/en/design/technical-documents/app-notes/4/4400.html