4

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

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

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

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

时间复杂度无关紧要。

4

3 回答 3

3

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

答案取决于估计随机选择集合的 M 个不同值中的最小值的概率{0, ..., N-1}，i对于每个可能的值i。调用这个值p(i, M, N)。有了比我耐心输入不支持 Latex 的界面更多的数学知识，您可以得出对该p函数的一些很好的估计；在这里，我将只展示简单的、不省时的方法。

让我们只关注p(0, M, N)，这是随机选择的M对象N将包括第一个对象的概率。然后我们可以一次遍历一个对象（即数字0...N-1）；通过翻转加权硬币来决定每个人是否包括在内。我们只需要计算每次翻转的硬币重量。

根据定义，有一组对象的可能选择。其中不包括第一个元素。（这是对象的-selections的计数，这是缺少一个元素的集合的所有-selections）。类似地，选择确实包括第一个元素（即 -set 的所有-selections ，第一个元素添加到每个选择）。MCNMNMCN-1MN-1MM-1CN-1M-1N-1

这两个值加起来；著名的计算递归算法。MCNC

p(0, M, N)只是. _ 因为，我们可以将该分数简化为。正如预期的那样，如果，则结果为 1（N 个对象中的 M 个必须包括每个对象）。M-1CN-1/MCNMCN = N!/(M!*(N-M)!)M/NM == N

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

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 循环执行直到Mis0
  • 越接近M，递减N的概率就越高。M如果我们达到了这样的地步M == N，那么两者都将同步递减，直到它们都达到0。
  • i恰好在N递减时递增，因此它必须始终在范围内0...N-1。事实上，它是多余的。我们可以输出N-1而不是输出i，这将改变算法以降序而不是升序生成集合。我没有这样做，因为我认为上面的内容更容易理解。

该算法的时间复杂度O(N+M)必须是O(N)。如果N很大，那不是很好，但是问题陈述说时间复杂度无关紧要，所以我把它留在那里。

于 2013-10-04T04:53:10.027 回答
1

不将其状态空间映射到较少位数用于输出的 PRNG 应该可以正常工作。示例包括线性同余生成器和 Tausworthe 生成器。如果您使用相同的种子启动它们，它们将给出相同的序列，但这很容易改变。

于 2013-10-03T23:29:43.073 回答
0

蛮力： 如果时间复杂度无关紧要，它将是 0 < M <= 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 个元素和 [r+1..N) (N2 个元素) 的 [0..r) 重复相同的步骤，选择 M1 和 M2 (M1+M2==M-1)，以便 M1/M2 == N1/N2。M1 和 M2 必须是整数，但是比例可以给出真实的结果，我们需要用概率四舍五入值（1.2 将给出 1 与 p=0.8 和 2 与 p=0.2 等）。

于 2013-10-03T23:59:13.297 回答