阿弥陀佛
分类： C/C++
2014-04-30 14:30:12
随机选取一个长度为N的链表（N很大）里的K个元素 - 编程珠玑
给你一个长度为N的链表。N很大，但你不知道N有多大。你的任务是从这N个元素中随机取出k个元素。你只能遍历这个链表一次。你的算法必须保证取出的元素恰好有k个，且它们是完全随机的（出现概率均等）。
以第k/m的概率抽取第m个元素，如果抽中该元素，那么再从k个已经被抽好的样本k中随机选择一个替换掉。
这样保证每个元素被抽中的概率为k/n。
计算公式为：
一个简单的版本是这样的：
如何在连续的网络流量中，等概率随机抽取1个数据包。由于这个数据包有多长并不清楚。所以你没法得到整个长度n。
先选取第一个元素，然后以1/m的概率抽取第m个元素，如果抽取成功则替换之前的抽样结果，这样保证了每次等可能的抽样。
第m个元素被选取的概率就等于第m个元素被选取×以后的元素不会被选取，公式如下：
