问题描述:
程序的输入包含两个整数m和n,其中m<n。输出是0~n-1范围内m个随机整数的有序列表,不允许重复。从概率的角度来说,我们希望得到没有重复的选择,其中每个选择出现的概率相等。
void GenerateKnuth(int m,int n) { int t=m; for(int i=0;i<n;i++) if(Rand(0,n-1-i)<t)//即以t/(n-i)的概率执行下面的语句 { printf("%d\n",i); t--; } }
其中Rand(a,b)随机产生[a,b]范围内的一个整数。
上述算法源自Knuth的《计算机程序设计艺术 第2卷 半数值算法》。Knuth 给出了概率上的证明,每个数选中的概率都是m/n,而且恰好选中m个数。
简单验证一下:
第0个数,被选中的概率是;
第1个数,被选中的概率是;
第2个数,被选中的概率是;
。。。