作者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