使用概率向数组中添加元素

Question

使用概率向数组中添加元素

3

我正在使用Python构建一个列表，例如，让我们说前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()中添加元素被加入列表的概率来实现。

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

- Vajjhala

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Dmitry Rubanovich · Accepted Answer

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+1)的机会被选择。经过第二轮迭代后，k+1有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)。第二次迭代后，k+1被选中的概率变成了k/(k+2)，而所有其他元素被选中的概率是k/(k+1)*((k-1)/k * k/(k+2) + 2/(k+2))= k/(k+2)。

实际上，这个算法会在第m步后将每个元素的概率折叠成k/(k+m)。