有什么方法可以做到这一点吗?
我的意思是,我们甚至无法使用 {0,1,..,N-1} 的“in”数组(因为它至少是 O(N) 内存)。
M 可以 = N。N 可以 > 2^64。结果应该是一致随机的,最好是每个可能的序列(但也可能不是)。
全范围 PRNG(和 friend )也不适合,因为它每次都会给出相同的序列。
时间复杂度无关紧要。
最佳答案
如果你不关心随机选择的顺序,那么它可以在常量内存中完成。选择按顺序出现。
答案取决于估计随机选择集合 {0, ..., N-1}
的 M 个不同值中的最小值的概率。是i
, 对于每个可能的 i
.调用此值 p(i, M, N)
.有了更多的数学知识,我没有耐心输入不支持 Latex 的界面,您可以得出一些关于 p
的相当不错的估计值。功能;在这里,我将只展示简单的、非时间效率的方法。
让我们只关注 p(0, M, N)
,这是随机选择 M
的概率来自 N
对象将包括第一个对象。然后我们可以一次一个地遍历对象(即数字 0...N-1
);通过掷一枚加权硬币来决定每个人是否包括在内。我们只需要计算每次抛硬币的重量。
根据定义,有<sub>M</sub>C<sub>N</sub>
可能 M
-一组选集 N
对象。其中<sub>M</sub>C<sub>N-1</sub>
不包括第一个元素。 (这是 M
的计数 - N-1
对象的选择,这是所有 M
- 集合中缺少一个元素的选择)。同样,<sub>M-1</sub>C<sub>N-1</sub>
选择确实包括第一个元素(即所有 M-1
-N-1
集的选择,第一个元素添加到每个选择)。
这两个值加起来是<sub>M</sub>C<sub>N</sub>
;著名的递归计算算法C
.
所以 p(0, M, N)
只是<sub>M-1</sub>C<sub>N-1</sub>/<sub>M</sub>C<sub>N</sub>
.自 <sub>M</sub>C<sub>N</sub> = N!/(M!*(N-M)!)
,我们可以将该分数简化为 M/N
.正如预期的那样,如果 M == N
,结果为 1(N 个对象中的 M 个对象必须包含每个对象)。
所以现在我们知道第一个对象出现在选择中的概率是多少。然后我们可以减少集合的大小,并减少或不减少剩余的选择大小,这取决于抛硬币是否确定我们包含或不包含第一个对象。所以这是最终的算法,在伪代码中,基于加权随机 bool 函数的存在:
w(x, y) => true with probability X / Y; otherwise false.
我将保留 w
的实现对于读者来说,因为它是微不足道的。
所以:
Generate a random M-selection from the set 0...N-1
Parameters: M, N
Set i = 0
while M > 0:
if w(M, N):
output i
M = M - 1
N = N - 1
i = i + 1
这可能不是很明显,但请注意:
output i
语句必须准确执行M
次,因为它与M
的递减相结合, while 循环执行到M
是0
- 越近
M
到达N
,M
的概率越高会递减。如果我们到了M == N
的地步,然后两者都将递减,直到它们都达到0
. -
i
恰好在N
时递增递减,因此它必须始终在0...N-1
范围内.事实上,这是多余的;我们可以输出N-1
而不是输出i
,这将改变算法以降序而不是升序生成集合。我没有那样做,因为我认为上面的内容更容易理解。
该算法的时间复杂度是O(N+M)
必须是 O(N)
.如果N
很大,这不是很好,但问题陈述说时间复杂度无关紧要,所以我会把它留在那里。
关于performance - 在小于 O(M) 的内存中从给定范围 0..N-1 生成 M 个不同的随机数(一次一个),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19170456/