当前位置：首页 > news >正文

【算法】【算法杂谈】从M个数中等概率的选出n个数，保证每一个数的选中概率都是n/m（蓄水池算法）

news 2025/8/24 11:34:08

前言

当前所有算法都使用测试用例运行过，但是不保证100%的测试用例，如果存在问题务必联系批评指正~

在此感谢左大神让我对算法有了新的感悟认识！

问题介绍

原问题
存在一个吐球的机器，该机器吐球的顺序是： 1号球，2号球，3号球…m号球,一共吐m个求
现在你有一个袋子，大小是n，n<m，当m个球吐完之后，你的袋子中应该有n个球，那么现在设计一个算法保证袋子中的n个球每一个球进入袋子中的概率都是相等的，都是n/m

解决方案

原问题：
解法很简单，证明在后面：
1、首先创建一个数组作为“袋子”，用来获取等概率的结果
2、循环将球放入袋子，在袋子装满之前，所有球都放入袋子
3、如果袋子满了，此时为第i个球，判断rand(i)是否大于n，如果小于袋子的大小，则随机找袋子中的某个位置覆盖，否则不放入
4、循环完成即可，此时袋子中每一个球放入的概率都是n/m

代码编写

java语言版本

原问题：
方法一:

/*** 二轮测试：蓄水池算法* @param k* @param max* @return*/public static int[] getKNumRandCp1(int k, int max) {int[] container = new int[k];// 初始化//for (int i = 0; i < max; i++) {//    container[i] = i + 1;//}for (int i = 0; i < max; i++) {if (i < k) {container[i] = i + 1;continue;}// 如果随机数没有超过k，则随机替换一个if (rand(i) <= k) {container[randCp1(k) - 1] = i;}}return container;}public static int randCp1(int num) {return (int)(Math.random() * num + 1);}public static void main(String[] args) {CommonUtils.printArr(getKNumRandCp1(5, 9));}

c语言版本

正在学习中

c++语言版本

正在学习中

思考感悟

如果不看证明我其实不知道为什么这样就一定是等概率的。
然后看了书里面的概率计算公式之后算是有些明白了：
首先我们看看第i号球如何才能被选中踢出去被n+1号球替换：
首先要满足两个条件：1、rand(n+1) < n 2、rand(n) = i
那么这两个事件的概率乘积就是i被k+1号球替换的概率：n/(n+1) * (1/n)
那么反过来，i球留下来的概率就是 1- 1/(n+1) = nn+1
同理可以计算出没有被n+2，n+3换出来的概率
n+2 ： (n+1)/(n+2)
n+3 : (n+2)/(n+3)
ok，如果在每一轮的随机下，最终i球留下来没有被替换出去，那么就算是i球被选中了，所以接下来我们求n轮后i号球留下来的概率即可
也就是从n+1一直到m，所有没有被换出去的概率乘积
n/n+1 * (n+1)/(n+2) * (n+2)/(n+3) … （m-1）/m= n/ m

这个概率刚好是等概率替换的概率，完美的证明~