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

Question

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

需要选择k(给定值)数以从具有n个数的给定集合S形成子集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