##随机抽样与洗牌算法 ###问题-选择抽样 给出一个数据流，这个数据流的长度很大或者未知。并且对该数据流中数据只能访问一次。请写出一个随机选择算法，使得数据流中所有数据被选中的概率相等。 ###解答 数据流一个接着一个的过来，根据一定的概率选择取或不取

数据流里只有一个数据，那么直接取该数据，概率为1

数据流里有两个数据，当第一个数据到达，取该数据，第二个数据达到，以1/2的概率取该数据，或者以1/2的概率取上一次取的数据。则数据流中数据被选中概率为1/2

数据流里有三个数据，当第一个、第二个数据到达，同上分析，当第三个数据到达，以1/3的概率取该数据，以2/3的数据取上一次的数据。则取到上一次数据的概率为2/3*1/2 = 1/3。

数据1被选中的概率1/2 * 2/3 = 1/3 数据2被选中的概率1/2 * 2/3 = 1/3 数据3被选中的概率1/3

所以假设选择算法为：当第n个数据到来时，以1/n的概率选择该数据，否则选中上一个数据。

推导：假设当有n-1个数据，假设成立，则选择其中一个数据的概率为1/(n-1)，当第n个数据到来，以1/n的概率选择该数据，否则以(n-1)/n选择上一个数据。则上一个数据被选择的概率为1/(n-1)*(n-1)/n=1/n，则每个数据选择的概率都为1/n。

###问题2-水库抽样 如果从数据流里以相同概率选中k个数据。

假设选择两个数据。

两个数据选两个，第一个数据到来，以概率1选中，第二个到来也以概率1选中。

三个数据，所求概率为2/3。第三个数据到来，以2/3的概率选中该数据，前两个数据被留下的概率为2/3*1/2=1/3。当1/3的概率没选中第三个数据，则前两个数据被留下的概率为1/3，综合两种情形，前两个数据被留下的概率为1/3+1/3 = 2/3。则每个数据被留下的概率都为2/3

###问题3-洗牌