作者：jostree 转载请注明出处 https://www.cnblogs.com/jostree/p/10274908.html
从n个数中等概率选取1个数，n未知
如果元素总数是n，那么每个元素备选到的概率应该是1/n, 然而N只有遍历结束时才会知道，于是我们可以利用乘法公式凑出1/n：
[p_i = frac{1}{i} imes frac{i}{i+1} imes frac{i+1}{i+2} imes dots imes frac{n-1}{n} = frac{1}{n}
]
在从前向后遍历的过程中，不断的根据概率改变我们的候选元素，第i个元素被最终选中的概率计算公式恰好为上式。
可以从代码简单实现：
class RandomSelectOne
{
public:
int count;
int selected;
RandomSelectOne():count(0){}
void add(int num)
{
count++;
if(rand() % count == 0)
selected = num;
}
int getSelected()
{
return selected;
}
}
从n个数中等概率的选取m个数，n未知
我们只需要把selected扩展成一个数组即可，对于第i个元素，其被选择的概率值为：
[p_i = frac{m}{i} imes frac{i}{i+1} imes dots imes frac{n-1}{n} i > m
]
[p_i = frac{1}{1} imes frac{m}{m+1} imes frac{m+1}{m+2} imes dots imes frac{n-1}{n} i leq m
]
对于前m个数，直接加入候选，这个数出现在最终候选名单的概率为每次加入新的值时，该数都没有没选中。对于m以后的数，被选进来的概率为m/i，在以后每次加入新数时，都没有被选中，即可以有上式表示。
代码如下：
class RandomSelect
{
public:
int count;
int scount;
vector<int> selected;
RandomSelect(int m):count(0), scount(m){}
void add(int num)
{
count++;
if(selected.size() < scount)
{
selected.push_back(num);
}
else
{
int idx = rand() % count;
if( idx < scount )
{
selected[idx] = num;
}
}
}
vector<int> getSelected()
{
return selected;
}
};
带权的n个数随机选取一个数的问题，n未知
设元素总数为n，当然在遍历结束前n是未知的。设第 (i(1 leq i leq n)) 个元素的权重为 (w_i) ，则权重总和为(w=sum_{i=1}^n w_i) ，也是在遍历结束时才知道的。根据题目要求，第(i)个元素被选取的概率应该等于(pi=frac{w_i}{w})。
如果最终被选择的是第i个元素，那么必须在遍历到它时，恰好被选中：
[frac{w_i}{w} = frac{w_i}{sum_{k=1}^i w_k}
]
另外，在处理后面的元素时，第i个元素没有被替换掉，对于任意的(j( i < j leq n ))，第i个元素都不会被选中，其概率为：
[frac{w-w_j}{w} = frac{sum_{k = 1} ^ {j - 1} w_k}{sum_{k = 1} ^ j w_k}
]
从而第i个元素最终被选择的概率为：
[p_i = frac{w_i}{sum_{k=1}^n w_i}
]
代码如下：
class RandomSelectOne
{
public:
double totalWeight;
int selected;
RandomSelectOne():totalWeight(0.0){}
void add(int num, double weight)
{
totalWeight += weight;
if(rand() % 10000 / 10000.0 * totalWeight < weight)
selected = num;
}
int getSelected()
{
return selected;
}
};
带权的n个数随机选取m个数，n未知
当m=2时，第i个元素被选中有两种情况，第一次被选中，第一次未被选中，第二次被选中，从而可以得到：
[p_i(2) = frac{w_i}{w} + sum_{j
eq i} (frac{w_j}{w} imes frac{w_i}{w-w_j})
]
也可以计算(ar{p})表示不被选中的概率：
[ar{p}_i(2) = sum_{j
eq i} (frac{w_j}{w} imes frac{w - w_j - w_i}{w - w_j})
]
很容易得到(p_i(2) + ar{p}_i(2) = 1)
当m>2时，元素i未被选中的概率为：
[ar{p}_i(m) = sum_{j_1}(frac{w_{j_1}}{w} sum_{j_2} ( frac{w_{j_2}}{w-w_{j_1}} sum_{j_3} (frac{w_{j_2}}{w-w_{j_1}-w_{j_2}} dots sum_{j_m} frac{w_{j_m}}{w - sum_{k=1}^{m-1} w_{j_k}})))
]