algorithm - 随机选择

Question

给定两个整数 N 和 n(N >= n > 0)，如何随机选择(不重复!)长度为 n 的 [0, N)？ 例如。给定 N = 5，n = 3 可能的解决方案是 (3,0,2) 或 (2,4,1) 等。

有一个限制阻止使用简单的方法:内存使用必须是 O(n)，而不是 O(N)。

/* 在天真的方法下，我的意思是使用 size=N 的临时数组，最初按顺序用数字 0..N-1 填充。从该数组中随机选择所需的 n 个项目。 */

Answer 1

遍历从 0 到 N 的所有数字 m，决定是否将遇到的 m 包含在集合中。您需要根据已处理的数字更新包含下一个数字的概率。

让我们将这个想法应用到给定的示例中，其中 n=3 和 N=5。首先考虑m=0。剩下 3 个数字和 5 种可能性，因此 0 在集合中的概率为 3/5。使用随机数生成器来决定是否包含该数字。现在考虑 m=1。如果你在集合中包括 0，那么你还有 2 个数字和 4 种可能性，所以它应该以 2/4 的概率被包括在内，但如果 0 不包括在内，你还有 3 个数字和 4 种可能性，因此应该包括 1概率为 3/4。这一直持续到集合中包含所需的 3 个数字。

这是 Python 中的一个实现:

from __future__ import division
import random

def rand_set(n, N):
    nums_included=set()
    for m in range(N):
        prob = (n-len(nums_included)) / (N-m)
        if random.random() < prob:
            nums_included.add(m)
    return nums_included

您可以(并且可能应该)添加一个测试来查看您的集合中何时有足够的数字，并尽早跳出循环。

数字存储在一个集合中，集合的大小从 0 到 n，因此使用的存储是 O(n)。其他一切都使用常量空间，因此总体上是 O(n)。

编辑实际上，您可以使用这种方法走得更远，因此它占用的空间是恒定的。在 Python 中，只需根据上面的内容制作一个生成器:

def rand_set_iter(n, N):
    num_remaining = n
    m = 0
    while num_remaining > 0:
        prob = num_remaining / (N-m)
        if random.random() < prob:
            num_remaining -= 1
            yield m
        m += 1

在这里，我继续使用 while 循环而不是 for 循环。要存储结果，您当然需要使用 O(n) 空间。但是，如果您需要做的只是遍历数字，生成器版本会在 O(1) 中完成。

对于没有生成器的语言，您可以推出自己的生成器，重复调用函数并更新静态或全局变量。