performance - 在小于 O(M) 的内存中从给定范围 0..N-1 生成 M 个不同的随机数(一次一个)

Question

有什么方法可以做到这一点吗？

我的意思是，我们甚至无法使用 {0,1,..,N-1} 的“in”数组(因为它至少是 O(N) 内存)。

M 可以 = N。N 可以 > 2^64。结果应该是一致随机的，最好是每个可能的序列(但也可能不是)。

全范围 PRNG(和 friend )也不适合，因为它每次都会给出相同的序列。

时间复杂度无关紧要。

Answer 1

如果你不关心随机选择的顺序，那么它可以在常量内存中完成。选择按顺序出现。

答案取决于估计随机选择集合 {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很大，这不是很好，但问题陈述说时间复杂度无关紧要，所以我会把它留在那里。