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

[LPH66 (-858993460)]

※ 引述《qeagle (神啊請讓我失戀吧)》之銘言：
: 請問這題要怎麼著手
: 我想產生一些亂數序列以供測試排序功能用
: 產生亂數簡單,但要保持其亂數產生順序,又不能有重覆..
: 不知道大家會怎麼寫好,先產生1000個,再一個個檢查有無重覆嗎...

: → james732:先建立一個陣列依序擺0-99999再隨機交換   140.117.171.46 05/25 21:16
: → james732:整個陣列弄亂了，挑前1000個即可          140.117.171.46 05/25 21:16
: → j094097:一邊產生一邊檢查跟前面有沒有重複也可      210.85.71.161 05/25 21:18
: 推 cooper6334:一樣是先陣列依序擺0-99999,然後抓亂數  111.252.104.88 05/25 21:57
: → WPC001:094097大的方法比較不好,會有機率不等的問   180.177.13.224 05/25 21:58
: → WPC001:題,用0-99999的陣列,然後彈出1000個較好     180.177.13.224 05/25 21:58
: → cooper6334:的時候就用for抓A[i]~A[99999]的值      111.252.104.88 05/25 21:59
: → cooper6334:再把抓到的值跟A[i]互換                111.252.104.88 05/25 21:59
: 推 zeat:http://tinyurl.com/o5uk3t 可以參考這個      122.118.34.155 05/26 07:25
唔  我得說演算法寫的不好的話

洗牌法也會有機率不等的問題

回頭檢查的缺點並不是機率不等

而是在於愈後面的數字產生所需的期望亂數個數會變多  以及檢查的比較時間

以這個問題來說  0~99999 取 1000 個數

平均得產生 1053.5 個亂數  以及約 50 萬個比較  效率上是個很大的問題

這在取的數字變多時會更明顯  例如取 5000 個數的話

平均需產生近 7000 個亂數  比較次數也上升到近二千萬次

至於洗牌法的話  cooper6334 的方法很標準

這等於是每次隨機從還沒抽的撲克牌中抽一張出來的感覺

如果你是不管範圍隨機選兩個數出來交換  那才會有機率不等的問題

--
  'You've sort of made up for it tonight,' said Harry. 'Getting the
sword. Finishing the Horcrux. Saving my life.'
  'That makes me sound a lot cooler then I was,' Ron mumbled.
  'Stuff like that always sounds cooler then it really was,' said
Harry. 'I've been trying to tell you that for years.'
                               -- Harry Potter and the Deathly Hollows, P.308

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.30.84
※ 編輯: LPH66           來自: 140.112.30.84        (05/26 09:23)
推 FRAXIS:洗牌法須要長度100000的陣列
→ FRAXIS:應該有只要存1000個就夠的方法吧
推 meto000:配合雜湊函數?
→ LPH66:配合雜湊的確是可以有效減少比較次數沒錯
→ LPH66:但是產生的亂數個數期望值卻不會減少