遍历从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)。

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