作者sevenjay (coder)
站内Programming
标题Re: [问题] 从0-99999选出一千个不重覆的乱数?
时间Wed May 26 18:33:04 2010
以实际上来看的话机率的确是不一样，假设是乐透49选6好了
法一：产生乱数索引，依索引取出，取出的抽走或互换
每个数的机率：
取第1个时机率是1/49
取第2个时机率是1/48
取第3个时机率是1/47
...
法二：先产生乱数，再检查有无重覆，决定要不要取
每个数的机率：
取第1个时机率是1/49
取第2个时机率是1/49
取第3个时机率是1/49
...
法二会有LPH66说得碰撞问题，要一直比较。
要看你的目的为何。
要模拟实际状况建议用法一。
效率的话要看m中取n，m跟n的比例多少来决定。
法一至少要swap n次，每swap一次要做3次赋予值运算，所以至少要3n。
n
法二比较次数至少要 Σ{i + i/m*i(比较次数+已取集合又取中的机率*比较次数)}。
i=1
如果以49取4的话法二的效率较好。
100000取1000的话法一的效率较好。
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 123.204.252.169
※ 编辑: sevenjay 来自: 123.204.252.169 (05/26 18:45)
1F：推 horngsh:用一个While true回圈不断产生乱数, 存进112.104.191.119 05/26 18:53
2F：→ horngsh:set中, 检查set长度, 满一千就结束LOOP112.104.191.119 05/26 18:55
3F：→ sevenjay:这样就是让set帮你做比较了，一样同法二123.204.252.169 05/26 19:28
4F：推 snowlike:所说法一为当下的条件机率并不影响总机率 114.33.184.50 05/26 20:05
5F：→ snowlike:法二的命中率分离出来其实和法一是一样的 114.33.184.50 05/26 20:05
6F：推 smallworld:法一计算错误 要用条件机率 123.193.77.208 05/26 20:51