随机选择

Question

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

有一个限制,阻止使用天真的方法:内存使用必须是O(n),而不是O(N).

/*在天真的方法下,我的意思是使用大小= 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).

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