随机地从大小为n的数组中选取m个整数

问题：写一个函数，随机地从大小为n的数组中选取m个整数。要求每个元素被选中的概率相等。

分析：这道题目和随机洗牌算法类似，只需要随机选取1个元素， 然后在剩下的元素里面随机选取下一个元素，不断这样操作即可。

这样做能保证每个元素选中的概率一样吗？也就是选中每个元素的概率都是1/n？ 答案是YES，让我们来做一下简单的计算。

选第1个元素：在n个中随机选，因此概率为1/n

选第2个元素：在剩下的n-1个中随机选：1/(n-1)，由于第1次没有选中它， 而是在另外n-1个中选：(n-1)/n，因此概率为：(n-1)/n * 1/(n-1) = 1/n

选第3个元素：同上：(n-1)/n * (n-2)/(n-1) * 1/(n-2) = 1/n

。。。。。

因此，按照这种方法选取k个元素，每个元素都是以1/n的概率被选出来的。代码如下： 选出的m个数放到数组前m个位置。

代码如下：

#include <iostream>#include <cstdlib>using namespace std;void Swap(int &a, int &b){// 有可能swap同一变量，不能用异或版本    int t = a;    a = b;    b = t;}void PickMRandomly(int a[], int n, int m){    for(int i=0; i<m; ++i){        int j = rand() % (n-i) + i;// 产生i到n-1间的随机数        Swap(a[i], a[j]);    }}int main(){    srand((unsigned)time(0));    int n = 9, m = 5;    int a[] = {        1, 2, 3, 4, 5, 6, 7, 8, 9    };    PickMRandomly(a, n, m);    for(int i=0; i<m; ++i)        cout<<a[i]<<endl;    return 0;}