0 .. n-1个数中随机选m个数

给定一个n, 一个m, 要求从0..n-1个数中随机选取m个数。

 

这里参考《编程珠玑》中的一个方法，既利用概率测试来进行选取。假设我们要从0到100中选取10个数。首先考虑0，我们选取它的概率为10/100 = 1/10，因此我们可以产生一个随机数（应该远远大于n），利用该数模100的值是否小于10来模拟选取0的情况。接着考虑1，这时我们应该根据0是否被选取来考虑其被选中的概率。

 

给出代码，补充了书中的bigrand的实现以及循环做了一点点改动。

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

int range_num;

unsigned int bigrand(void){
    srand(time(NULL));
    return (unsigned int)(100 * range_num * rand());
}

int main(void){
    int m = 10, n = 1000;    
    int i, remaining = n, select = m;

    range_num = n;

    for(i = 0;i < n && select > 0;i++){
        if(bigrand() % remaining < select){
            select --;  
            printf("%d ",i);
        }   
        remaining--;
    }   
    
    printf("\n");
    return 0;
}