数组中随机选择n个数

转自：http://blog.csdn.net/pipi666661/article/details/16114599

php的话，已经实现了这个功能，直接用array_rand()就可以返回随机的数组下标了。然后打印出来就ok。

<?php

function rand_me(array $a ,$n){
        $rand_keys = array_rand($a, $n);
return $rand_keys;
}


$input = array("hi", "hello", "test", "a", "b");
srand((float) microtime() * 10000000);
$n=2;
$rand_keys=rand_me($input,$n);

for($i=0;$i< $n;$i++){
print $input[$rand_keys[$i]] . "\n";
}


?>

不过array_rand()是如何实现的呢，下面用c++写的段代码。

#include <iostream>
#include <cstdlib>
using namespace std;
void Swap(int &a, int &b){// 有可能swap同一变量，不能用异或版本
    int t = a;
    a = b;
    b = t;
}

/*这样做能保证每个元素选中的概率一样吗？也就是选中每个元素的概率都是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个位置。
*/



//方法一：直接改变数组
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]);
    }
}


//方法二：产生keys 不影响原来数组
void randkeys(int a[],int *b, int n, int m){
    for(int i=0; i<m; ++i)
     { int j = rand() % (n-i) + i;// 产生i到n-1间的随机数
        Swap(b[i], b[j]);
    }

}



int main(){
    srand((unsigned)time(NULL));
    int n = 9, m =9;

    //方法一：随机选择key，与i交换，改变数组a的值
    //初始a为1-n
    int a[n];
    for(int i=0;i<n;i++)
    {
            a[i]=i+1;
     }
    PickMRandomly(a, n, m);
    cout<<"方法一：======="<<endl;
    for(int i=0; i<m; ++i)
        cout<<a[i]<<" ";
    cout<<endl;

     //方法二：随机选择key，用数组b来记录每次选择的key，a数组不改变
     //初始a为1-n  b为a的下标
    int b[n];
    for(int i=0;i<n;i++)
          { b[i]=i;
            a[i]=i+1;

     }
    randkeys(a, b,n, m);
    cout<<"方法二：======="<<endl;
    for(int i=0; i<m; ++i)
        cout<<a[b[i]]<<" ";

    system("pause");
    return 0;
}