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

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

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

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

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

时间复杂度无关紧要。

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

答案取决于估计随机选择集合{0, ..., N-1}的 M 个不同值中的最小值i的概率，对于每个可能的i。将此值称为 p(i, M, N) 。有了比我有耐心输入不支持 Latex 的界面的数学，你可以对 p 函数得出一些相当不错的估计;在这里，我将只展示一种简单、不省时的方法。

让我们只关注 p(0, M, N) ，即从N对象中随机选择M将包含第一个对象的概率。然后我们可以一次迭代一个对象(即数字0...N-1(;通过掷出加权硬币来决定是否包括它。我们只需要计算每次翻转的硬币重量。

根据定义，一组N对象_MC_N可能的M选择。其中_MC_N-1不包括第一个元素。(这是N-1对象的M个选择的计数，这是缺少一个元素的集合的所有M选择(。同样，_M-1C_N-1选择确实包括第一个元素(即，N-1 -set 的所有M-1 -选择，第一个元素添加到每个选择中(。

这两个值加起来就是_MC_N;这是众所周知的用于计算C的递归算法。

所以p(0, M, N)只是_M-1C_N-1/_MC_N.自_MC_N = N!/(M!*(N-M)!)年以来，我们可以将该分数简化为M/N。正如预期的那样，如果M == N，则计算为 1(N 个对象中的 M 个必须包含每个对象(。

所以现在我们知道第一个对象在选择中的概率是多少。然后，我们可以减小集合的大小，并减少剩余的选择大小，具体取决于硬币翻转是否确定我们是否包含第一个对象。所以这是伪代码中的最终算法，基于加权随机布尔函数的存在：

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很大，那不是很好，但问题陈述说时间复杂度无关紧要，所以我把它留在那里。

不将其状态空间映射到较低数量的输出位的 PRNG 应该可以正常工作。示例包括线性全等生成器和陶斯沃思生成器。如果您使用相同的种子来启动它们，它们将给出相同的顺序，但这很容易更改。

蛮力：如果时间复杂度无关紧要，它将是 0 <= N 不变量的解决方案。nextRandom(N( 是一个返回 [0..N] 中的随机整数的函数：

init() {
        for (int idx = 0; idx < N; idx++) {
            a[idx] = -1;
        }
        for (int idx = 0; idx < M; idx++) {
            getNext();
        }
    }
    int getNext() {
        for (int idx = 1; idx < M; idx++) {
            a[idx -1] = a[idx];
        }
        while (true) {
            r = nextRandom(N);
            idx = 0;
            while (idx < M && a[idx] != r) idx++;
            if (idx == M) {
                a[idx - 1] = r;
                return r;
            }
        }
    }

O(M( 解决方案：它是简单的递归解决方案。它假设运行 nextRandom((，它返回 [0..1] 中的随机数：

rnd(0, 0, N, M); // to get next M distinct random numbers
int rnd(int idx, int n1, int n2, int m) {
    if (n1 >= n2 || m <= 0) return idx;
    int r = nextRandom(n2 - n1) + n1;
    int m1 = (int) ((m-1.0)*(r-n1)/(n2-n1) + nextRandom()); // gives [0..m-1]
    int m2 = m - m1 - 1;
    idx = rnd(idx, n1, r-1, m1);
    print r;
    return rnd(idx+1, r+1, n2, m2);
}

这个想法是在第一步中在 [0..N( 之间选择一个随机 r，它将两个子范围的范围按每个子中的 N1 和 N2 元素拆分 (N1+N2==N-1(。我们需要对具有 N1 元素的 [0..r( 和 [r+1..N((N2 元素(重复相同的步骤，选择 M1 和 M2 (M1+M2==M-1(，以便 M1/M2 == N1/N2。M1 和 M2 必须是整数，但比例可以给出实际结果，我们需要用概率对值进行四舍五入(1.2 将给出 1，p=0.8,2 在 p=0.2 等情况下(。

相关内容

最新更新

热门标签：