从 Steven Skiena 的算法设计手册中得到这个问题。
要求从给定的n个数集合S中选出k(给定值)个数组成子集S',使得每个数的选择概率都相等(k/n)。 n 是未知的(我正在考虑将 S 作为链接列表)。 同样,我们只能通过集合 S。
最佳答案
当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
关于algorithm - 从集合中以相等概率选择数字,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8516664/