【蓄水池问题】太 nice 了！我中奖啦！

小伙伴们中过奖么？

是不是都是 中奖绝缘体 呢？

今天我们就来聊一聊关于中奖的 概率 问题~

先思考两个问题

如果让你从规模为 N 的数据序列中，随机选取出 k 个不重复的数据，你会怎么做呢？

• 是不是很简单，知道了总数 N ，等概率随机选择 k 个即可，每个数据被选到的概率均为 $k/N$ 。

问题变一下：那如果从始至终都不知道 N 的具体大小呢？也就是说，数据流长度 N 很大，数据会源源不断的到来，且 N 直到处理完所有数据之前都不可知。

如何在这样的情况下，随机选取 k 个数据，保证当前已经到来的前 i 个元素中每一个元素被选中的概率相等，均为 $k/i$ ，当处理完所有数据结束时，概率自然就变为了 $k/N$ 呢？

两者区别一句话总结：能否提前知道 总数据量 N 。

这就引出了今天要探讨的问题：蓄水池算法

蓄水池算法

在一个很大，未知总量的数据流中，抽取 k 个样本，并保证每个样本的选取概率都是 相等并随机 的。

算法思路

1. 构建一个可容纳 k 个样本的数组容器。
2. 当数据量不足 k 个时，全部选取放入数组中。
3. 当数据量超过 k 个时（假设是第 i 个元素），以 $k/i$ 的概率选择进入数组中，并以 $1/k$ 的概率随机替换掉数组中的一个样本元素。
4. 无论样本数据 N 何时结束，均能保证所选元素概率均为 $k/N$ 。

即：保证在动态情况下，已经到来的每个样本元素被选中的概率相等

证明

当 $i\le k$ 时，前 m 个元素，每个被选到的概率均为 $k/m$ 。

当 $i＞k$ 时，前 m 个元素，每个被选到的概率也均为 $k/m$ 。

由以上两种情况的证明，我们可以得出结论：

每个元素被选到的概率均等，均为 $k/N$ 。

以上我们证明了该方法的正确性：能够在未知数据量的情况下，依然保证在新元素到来时被选中的概率相等。

代码

public static class RandomBox {
    // 存放被选的元素数组
    private int[] arr;
    // 抽取 k 个样本
    private int k;
    // 目前到达的样本总数
    private int m;

    // 初始化
    public RandomBox(int capacity) {
        arr = new int[capacity];        
        k = capacity;        
        m = 0;
    }

    // 等概率随机 1 ~ max 之间的一个数
    private int rand(int max) {
        return (int) (Math.random() * max) + 1;
    }

    // 新到一个元素后，进行选择
    public void add(int num) {
        // 总量+1
        m++;
        // 没超过k时，直接选入
        if (m <= k) {
            arr[m - 1] = num;
        } else {
            // 以 k/i 的概率选择进入数组
            if (rand(m) <= k) {
                // 随机替换掉其中一个元素，概率 1/k
                arr[rand(k) - 1] = num;
            }
        }
    }
    
}

实际意义

这个算法在现实中有什么意义呢？
抽奖

参与活动中大奖：

今天所有参与活动的小伙伴都有几率中奖哦，今晚24：00整开奖~

假设设置了 10 个奖品，但不知道有多少个人会来参与活动，当 24：00 整时，要公布获奖名单。

此时，就可以选择“蓄水池算法”，活动结束后，遍历一遍结果数组 arr[10]，所有在数组中的 10 个人就是最终的获奖者。每个人的中奖几率均为 10/今天参与活动的总人数 ，确保了活动的公平性。

你中过奖么😜
~ 点赞 ~ 关注 ~ 星标 ~ 不迷路 ~！！！

关注
回复「ACM紫书」获取 ACM 算法书籍 ~
回复「算法导论」获取 算法导论第3版 ~

点赞、转发
让你的小伙伴们一起来学算法吧！！