以相同的概率从集合中选择数字

Question

从 Steven Skiena 的算法设计手册中得到这个问题。

要求从给定的n个数字的集合S中选择k(给定值)个数字形成子集S'，使得每个数字的选择概率相等(k/n)。 n 未知（我正在考虑将 S 作为一个链接列表）。 而且，我们只能通过集合S。

Answer 1

当n 未知时，您宁愿需要一个在线算法来进行所谓的储层采样。

很好的解释&这里提供了证明草图 http://propersubset.com/2010/04/choosing-random-elements.html

我的意思是用Python实现的这个算法（取自上面的链接）

import random
def random_subset( iterator, K ):
    result = []
    N = 0

    for item in iterator:
        N += 1
        if len( result ) < K:
            result.append( item )
        else:
            s = int(random.random() * N)
            if s < K:
                result[ s ] = item

    return result

Answer 2

像这样的

for elem in S
  if random() < (k - S'.size)/S.size // This is float division
    S'.add(elem)

第一个元素以概率 k/n 选择，第二个元素以 (nk)/n * k/(n-1) + k/n * (k-1 )/(n-1) 减少为 k/n 等。

Answer 3

您应该选择一个能够真正模拟真实活动“从n个数字中随机选择k个数字”的算法。您的算法应该具有两个属性

（1）它必须最后返回k个数字。

(2)它必须真实地模拟目标活动的属性：每个数字都是以概率k/n选择的。

Oborok的答案是错误的，因为它没有第一个属性。

for i = 0 to n
randomly choose an integer number between [1,n-i+1]
if [randomValue <= (k - S'.size)/(S.size - i + 1)] then
    S'.add(S[i])

通过上述选择方案，每个数字都以 k/n 的概率被选择。通过证明下面的等式可以看出：

https://www.facebook.com/photo.php?fbid=677984275648191&l=7cafe5d468