algorithm - 从集合中以相等概率选择数字

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