怎么产生n个不重复等概率随机数??

egmkang

记得以前在哪里看到过,忘了,特来问问.
随即整数,小于某个常量C,n<C的.
要求不能重复,而且数字出现的概率相等.

谢谢了

egmkang

哦,还有一条,要求时间复杂度的....
O(N^2)是个人都能做.....

克拉玛依

查找。

yecheng_110

建立一个数组[0..c) 然后打散它 然后一个一个的取

daybreakcx

一个经典的方法大概是这样的：

1. for (i = 0; i < n; i++)
   
2.         x[i] = i;
   
3. for (i = 0; i < n - 1; i++) {
   
4.         j = rand(n - i - 1);
   
5.         temp = x[i];
   
6.         x[i] = x[j];
   
7.         x[j] = temp;
   
8. }

复制代码

原先是从0到n-1中取m个不重复的随机样本，这里m为n的时候应该就是你要的一个解

egmkang

回复 5# daybreakcx


    昨天晚上想到了,就一个洗牌算法.
这样能保证是等概的嘛?

cjaizss

回复  daybreakcx


    昨天晚上想到了,就一个洗牌算法.
这样能保证是等概的嘛?
egmkang 发表于 2010-03-01 08:19

   如果rand函数是等概的,则以上算法所得到的每个排列是不等概的.

emacsnw

回复 1# egmkang


    设f(C, n) 为1 .. C中n个不重复的随机数 (n <= C).

那么 f(1, 1) = { 1 }.
当 C > 1 时：
  令u ~ uniform(0, 1)
  f(C, n) = {C, f(C - 1, n - 1)} if u < n / C
  f(C, n) = {f(C - 1, n)} otherwise

雨过白鹭洲

这个题太高难了。。

凡是算法的都是我不能解决的

daybreakcx

回复  daybreakcx


    昨天晚上想到了,就一个洗牌算法.
这样能保证是等概的嘛?
egmkang 发表于 2010-03-01 08:19

1. for (i = 0; i < n; i++)
   
2.         x[i] = i;
   
3. for (i = 0; i < n - 1; i++) {
   
4.         j = i + rand(n - i);//change here
   
5.         temp = x[i];
   
6.         x[i] = x[j];
   
7.         x[j] = temp;
   
8. }

复制代码

原先程序取j的时候有点错误，改正如上，可以保证等概率，只要rand等概率，证明如下：
每次选取从i到n-1的n-i个数值来交换，所以
对于x[0]，取每个数值的概率是1/n（在n个数值中取一个）
对于x[1]，取每个数值的概率是1/(n-1)*(n-1)/n=1/n，之所以不是1/(n-1)是因为要在保证x[0]没有取到这个值的情况之下((n-1)/n)，等概率取剩下n-1个数值，n-1就削掉了
……以下由此类推
每次对于x取t的概率都是保证x[0]没取t时(n-1)/n，x[1]也没取t时(n-2)/(n-1)，...，x在剩下的n-i个数值中取到t的概率1/(n-i)的乘积，所以大家都是1/n.