Re: [問題] 從0-99999選出一千個不重覆的亂數?
以實際上來看的話機率的確是不一樣，假設是樂透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)
推
05/26 18:53, , 1F
05/26 18:53, 1F
→
05/26 18:55, , 2F
05/26 18:55, 2F
→
05/26 19:28, , 3F
05/26 19:28, 3F
推
05/26 20:05, , 4F
05/26 20:05, 4F
→
05/26 20:05, , 5F
05/26 20:05, 5F
推
05/26 20:51, , 6F
05/26 20:51, 6F
討論串 (同標題文章)
完整討論串 (本文為第 3 之 9 篇)：