python - 以概率向数组添加元素

Question

所以我正在用 Python 构建一个列表，例如，让我们说前 100 个整数，但我确实需要所有 100 个整数，但只有一个样本可以说是 3。

import random 

def f():
    list_ = []
    for i in range(100):
        list_.append(i)
    return list_

def g(list_,k):
     return random.sample(list_, k)

print(g(f(),3))

>>>[50, 92, 6]

现在我可以不用首先构建整个列表，而是直接构建样本，也许可以通过在 f()

因为如果我要构建一个不是整数而是一些其他对象的巨大列表，这种方法在内存和计算方面的成本可能很高。

Answer 1

def random_no_dups_k_of_n(k, n):
    res = list(range(k))
    for i in range(k, n):
        v = random.randint(0, i) # this is 0-i inclusive
        if v == i:
            ir = random.randint(0,k-1)
            res[ir] = i
    return res

这里发生了什么:它是一种伸缩式产品。从 0 到 k-1 的每个元素开始时都有 k/k 的机会被选中。在第一次迭代之后，k 有 1/(k+1) 机会被选中，而 所有 其他人(不仅仅是剩下的，而是所有的)都有(k-1)/k * k/(k+1) = (k-1)/(k+1) 被选中的机会。第二次迭代后，k+1 有 1/(k+2) 机会被选中，而所有其他人都有 (k-1)/(k+1) * (k+1)/(k+2) = (k-1)/(k+2) 被选中的机会。等等。最后，每个号码都有 k/n 的机会被选中。

实际上，我刚刚看到您可以执行 random.sample(range(n), k)。我只是假设它不可用。

编辑:我在上面得到了相反的概率。正确的版本应该是:

def random_no_dups_k_of_n(k, n):
    res = list(range(k))
    for i in range(k, n):
        v = random.randint(0, i) # this is 0-i inclusive
        if v < k:
            ir = random.randint(0,k-1)
            res[ir] = i
    return res

从 0 到 k-1 的每个元素开始时都有 k/k 的机会被选中。在第一次迭代后，k 有 k/(k+1) 机会被选中，而 所有 其他人(不仅仅是剩下的，而是所有的)都有k/k*((k-1)/k * k/(k+1) + 1(k+1) = k/(k+1) 被选中的机会。在第 2 次之后迭代，k+1 有一个 k/(k+2) 机会被选中，而所有其他人都有一个 k/(k+1)* ((k-1)/k * k/(k+2) + 2/(k+2))= k/(k+2) 被选中的机会。

这实际上确实折叠了所有计算，以便在第 m 步后为每个元素提供 k/(k+m) 机会。