等概率选取问题 Random Pick

选取问题是：从元素个数为N的集合中随机选取K个，这里要求是不重复的选取。等概率选取问题要求保证选取的随机性，即集合中每个元素被选取的概率都相等。下面是两个常见的方法。

方法一：保证了

按顺序选取

，即把被选出的K个元素从左到右的顺序依次选出。当然N是事先已知的。

方法二：保证了在

事先不知道N为多少

的情况下，只扫描一遍就选出K个元素。当然没有保证选出的K个元素是按原顺序排列的。

方法一：

对于整数m和n，其中m<n，输出0~n-1范围的整数中m个随机值的有序列表，不允许重复。

 void GenRandom(int m, int n) 
 { 
         for(int i=0; i<n; ++i) 
         { 
                 if((bigrand()%(n-i)) < m) 
                 { 
                         cout<<i<<endl; 
                         --m; //只有被选中时m才自减
                 }
         }
 }

0被选取的概率：m/n1被选取的概率，分别看0被选中或不被选中的情况：(n-m)/n * m/(n-1) + m/n * (m-1)/(n-1) = m/n

2被选取的概率，分别看0，1是否被选中的情况：(m-2)/(n-2) * m/n * m/n + (m-1)/(n-2) * m/n * (n-m)*2/m + m/(n-2) * (n-m)/n * (n-m)/n = m/n

……

从0~n-1依次计算每个i被输出的概率，发现都是m/n，因此是等概率的随机选取。

方法二：

有一个长度为N的链表，N未知。要求只遍历一次链表，就从链表中等概率的挑出K个数（K<N），不允许重复。