Re: [問題] 從0-99999選出一千個不重覆的亂數?

[sevenjay (coder)]

以實際上來看的話機率的確是不一樣，假設是樂透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)
推 horngsh:用一個While true迴圈不斷產生亂數, 存進
→ horngsh:set中, 檢查set長度, 滿一千就結束LOOP
→ sevenjay:這樣就是讓set幫你做比較了，一樣同法二
推 snowlike:所說法一為當下的條件機率並不影響總機率
→ snowlike:法二的命中率分離出來其實和法一是一樣的
推 smallworld:法一計算錯誤 要用條件機率