以相同的概率从一组中选择数字

从Steven Skiena的算法设计手册中得到了这个问题。以相同的概率从一组中选择数字

要求通过选择K（值给出）编号，以从具有n个编号，给定的集合S形成一个子集S”，使得对于每个号码选择概率等于（K/N）。 n是未知的（我正在考虑将S作为链接列表）。也，我们可以有仅通过集合S

2011-12-15 S..K

基本上相同http://stackoverflow.com/questions/5416567/random-selection/5417178＃5417178 – 2011-12-15 08:18:21

我认为问题是不同的，因为n是未知的。 – xdavidliu 2016-09-05 22:38:43

像这样

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

第一元件被选择的概率k/n，第二个与(n-k)/n * k/(n-1) + k/n * (k-1)/(n-1)这减少了k/n等

来源

2011-12-15 07:57:43

当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

来源

2012-05-04 13:34:51 Alec

你应该选择一种算法，可以真正模拟真实的（从上面的链接所）活动。您的算法“随机从n个数字中选择k个”应该有两个属性

月底（1）它必须返回k个。

（2）必须真实地模拟该靶活性的性质：每个数字被选择的概率是K/N。

Oboroks answer is wrong because it hasn吨第一属性。

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.You选择可以看到，通过证明下面的等式：

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

来源

2014-10-09 17:35:04

以相同的概率从一组中选择数字

回答

相关问题