水塘抽样算法和Fisher–Yates算法

水塘抽样算法

公司尾牙的抽奖程序，我代码已经写好了。给公司的一些总工看了一下核心的抽奖代码，其中一个总工提出了“水塘抽样”算法来解决随机性和公平性的问题，所以就有了这篇博客。

参考链接里有非常清晰的分析，主要是使用了数学归纳法，将复杂的问题先简单化，高中数学知识，不过我已经忘了。算法的实现并不难，下面是我用js的实现：

var all = [1,2,3,4,5,6,7,8,9,0]
var k = 5
var sampling = all.slice(0, k);
for (var i = k; i < all.length; i++) {
    var m = Math.floor(Math.random() * (i + 1))
    if (m < k) {
        sampling[m] = all[i]
    }
}
console.log(sampling);

最有意思的是数学论证，可以查看维基百科。

水塘抽样的特点

• 适合样本很大且不知道数量的情况，上面的例子模拟的是样本有限的情况。

Fisher–Yates算法

Fisher和Yates分别表示两个人名，算法是这两个人发明的，大概的思想类似桌面上有一堆牌，我们随机从里面抽取一张出来，放到另外一堆，重复这个过程直到完成。放到代码里来描述这个想法，就要建立两个数组，性能不好，所以这个算法又有了一些新的演变，lodash的实现就是演变后的实现。

lodash的源码在这里：

https://github.com/lodash/lodash/blob/master/shuffle.js

参考链接

Reservoir sampling（水塘抽样）

https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

由乱序播放说开了去-数组的打乱算法Fisher–Yates Shuffle

洗牌算法Fisher–Yates shuffle