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

egmkang

回复 19# A.com

两个数,其中选取一个.
现在已经选了0个,那选取下一个(即最后一个)数,任何一个数出现的概率均是1/2.


正面的反驳我暂时没想到,高中的知识全忘了...汗

emacsnw

... 好像看过的  bit[c];
sum = 0;
v += rand(); 从0 开始循环。 如果bit[v] = 1;
go on, 命中 sum+1；
...
benjiam 发表于 2010-02-28 22:57

    这是所谓的rejection sampling. v+=rand()步进是不需要的，每次都随机选择一个1 .. C中的整数k，检查如果bit[k] = 0就设成bit[k] = 1就可以了。这样的算法适合n << C的情况。当n接近C的时候rejection概率会非常高。算法效率成问题。

peidright

回复 14# emacsnw

擦，本来写了准备回复一大版，说明你证明的一个错误，结果发现自己理解错了。这个方法确实好。很恢弘大气的一个方法。佩服。

peidright

回复 19# A.com


    等概率的意思是，最终结果上看来，每个数的概率相等。或者弱一点说，多次进行这样的实验，形成k组数，然后每个数站的比率平均。
   从n个数里面选 n个不同数，最终看来，本来每个数被选中的概率就是1.

egmkang

回复 19# A.com

C个数,选取n个,出现某一个数字A的概率是:
1. 第一个数就是A,概率是1/C;第一个数不是A,概率是(C-1)/C;
2. 第二个数是A,概率是(C-1)/C*1/(C-1)=1/C;也不是A的概率是(C-1)/C*(C-2)/(C-1)=(C-2)/C
3. 设第i个数是A的概率是1/C,不是A的概率是(C-i)/C.
    那么第i+1个数是A的概率是:
    (C-i)/C*1/(C-i)=1/C
    不出现A的概率是
    (C-i-1)/C.
4. 下来是那个递归法的后面步骤.....

所以,每一个数字出现A的概率均为1/C,那么选取n个数,出现A的概率就是n/C.

peidright

回复 25# egmkang


    这样说明似乎是没错，但是不是精髓。 emacsnw 考虑的时候，根本不是这样考虑的，从c个数中选n个数，
最终的结果，肯定是每个数的概率必须是n/c,这个是不需要说明和任何证明的。因为这是题目等概率的自然要求。
反过来说，我们只要保证，c以概率为n/c选中或者以1-n/c不选中,问题就解决好。很大气的方法。

cjaizss

其实这个问题是个彻头彻尾的概率问题,并且不难,学点概率论就啥都明白了。

A.com

回复  A.com

两个数,其中选取一个.
现在已经选了0个,那选取下一个(即最后一个)数,任何一个数出现的概率 ...
egmkang 发表于 2010-03-01 20:07

   如果你已经选出了一个，那么在选第二个的时候你还有选择么？

pppStar

好贴！

翻译 emacsnw 的算法为C实现以助兴！：）

1. #include <stdlib.h>
   
2. #include <stdio.h>
   
3. #include <time.h>
   
4. 
   
5. static int* parray = NULL;
   
6. static int arraysize = 0;
   
7. 
   
8. double uniform01()
   
9. {
   
10.         return ((double) rand() /(double) RAND_MAX) * 1 + 0;
    
11. }
    
12. 
    
13. void initset(int* pa, int asize)
    
14. {
    
15.         int i =0;
    
16.         for(i = 0;i < asize;i++)
    
17.         {
    
18.                 pa[i] = 0;
    
19.         }
    
20. }
    
21. 
    
22. void showset(int* pa, int asize)
    
23. {
    
24.         int i =0;
    
25.         for(i = 0;i < asize;i++)
    
26.         {
    
27.                 printf("%d ", pa[i]);
    
28.                 if((i != 0) && ((i+1)%8 == 0))
    
29.                 {
    
30.                         printf("\n");
    
31.                 }
    
32.         }
    
33. 
    
34.         printf("\n");
    
35. 
    
36. }
    
37. 
    
38. void addset(int* pa, int asize, int a)
    
39. {
    
40.         int i =0;
    
41.         for(i = 0;i < asize;i++)
    
42.         {
    
43.                 if(pa[i] == 0)
    
44.                 {
    
45.                         pa[i] = a;
    
46.                         break;
    
47.                 }
    
48.         }
    
49. }
    
50. 
    
51. void f(int c, int n)
    
52. {
    
53.         double u = uniform01();
    
54.         int a = 0;
    
55. 
    
56.         if(c > 0 && n > 0)
    
57.         {
    
58.                 if(c == 1 && n == 1)
    
59.                 {
    
60.                         addset(parray, arraysize, 1);
    
61.                 }
    
62.                 else
    
63.                 {
    
64.                         if(u < (double)((n*1.0)/(c*1.0)))
    
65.                         {
    
66.                                 addset(parray, arraysize, c);
    
67.                                 f(c-1, n -1);
    
68.                         }
    
69.                         else
    
70.                         {
    
71.                                 f(c-1, n);
    
72.                         }
    
73.                 }
    
74.         }
    
75. }
    
76. 
    
77. int main(int argc, char* argv[])
    
78. {
    
79.         int c, n;
    
80.         printf("Plaese input C:");
    
81.                 scanf("%d",&c);
    
82.         printf("\n");
    
83. 
    
84.         printf("Plaese input n:");
    
85.                 scanf("%d",&n);
    
86.         printf("\n");
    
87. 
    
88.         parray = (int*)malloc(n*sizeof(int));
    
89.         arraysize = n;
    
90.         initset(parray, arraysize);
    
91.         srand( (unsigned)time( NULL ) );
    
92. 
    
93.         f(c,n);
    
94. 
    
95.         showset(parray, arraysize);
    
96.         free(parray);
    
97. 
    
98.         //system("pause");
    
99. 
    
100.         return 0;
     
101. }

复制代码

附上一些rejection sample的文章，数学真的好难哦
random.rar (967.79 KB, 下载次数: 58)

2010-03-02 11:25 上传

点击文件名下载附件

deargodzw

不重复，等概率？只要事先都不知道数是多少，那么不管你怎么抽都是等概率的。应该就是打乱这个n个数就可以了吧