生成不重复的随机数

问题：生成[0,N-1]区间内的n个互不相同的随机数。 解决思路：首先，生成一个长度为N的数组，然后将其打乱，取前n个数，即为上述问题的解。 为了验证上述方法产生的随机数是符合要求的，我们用下面的方法来检验。 每次随机的从[0,N-1]中选取n个数，记它们的和为X,则X的期望可以计算如下： 这样选取n个数总共有$C_N^n$中取法，这么多取法总共取出了$C_N^n\ast n$个数，而0，1，2，…N-1这N个数出现的概率是相同的，因此每个数出现了$\frac{n\ast C_N^n}{N}$次，于是它们的和为 $\frac{(1+N)\ast N}{2}\ast \frac{n\ast C_N^n}{N}=\frac{1+N}{2}\ast n\ast C_N^n$ 故X的期望E(X)为 $E(X)=\frac{(1+N)\ast n}{2}$ 下面是代码：

#include<iostream> #include<cstdlib> #include<ctime> #pragma GCC optimize(3,"Ofast","inline") using namespace std; void generate_non_repeat_n_random_num(int n,int N,int *arr){ //生成介于0-N之间的n个不重复的随机数 srand(time(0)); for(int i=0;i<N;i++) arr[i]=i; for(int i=0;i<N;i++) { int j=rand()%(N-i)+i; //m=i,i+1,i+2,...,N-1 if(i!=j){ int tmp=arr[i]; arr[i]=arr[j]; arr[j]=tmp; } } } int main(){ int n,N; int *arr; int cnt; cout<<"Input N and n:"; cin>>N>>n; cout<<"Input cnt:"; cin>>cnt; arr=new int[N]; generate_non_repeat_n_random_num(n,N,arr); int i=0; long long sum=0; while (i++<cnt) { generate_non_repeat_n_random_num(n,N,arr); for(int j=0;j<n;j++) sum+=arr[j]; } cout<<sum/(double)cnt<<endl; cout<<(N+1)*n/2<<endl; system("pause"); return 0; }

运行结果如下 可以看到，X的平均值和理论期望值十分接近，说明该方法符合要求。