从N个数总随机选出M个数

来自编程珠玑

问题：假设一组数0,1,2,3,.....N-1，随机选出M个不重复的数字

开始0 被选择的概率为  M/N

1被选择的概率为  M/N(如果0没有被选择的话)  或者 M-1/N(0被选择了)

当到i 的时候被选择的概率为 剩余的数用r表示，要选择出的数用s,则其概率为 s/r

开始的时候 r=N s=M

if(rand()%r<s)------>概率为s/r    当rand()在0,1,2,....r-1 的时候，成立

 当前i被选择  r--  s--;

否则的话  r--;

代码：

void fun2(int n,int m)//从0---n-1中选m个元素
{
	int i;
	int k;
	int select=m;
	int remaining =n;
	for(i=0;i<n;i++)
	{
			srand((unsigned)time(NULL));
			k=rand();
			if(k%remaining<select)
			{
				cout<<i<<endl;;
				select--;
				
			}
			remaining--;
			
	}

}