※ 引述《qeagle (神啊請讓我失戀吧)》之銘言： : 請問這題要怎麼著手 : 我想產生一些亂數序列以供測試排序功能用 : 產生亂數簡單,但要保持其亂數產生順序,又不能有重覆.. : 不知道大家會怎麼寫好,先產生1000個,再一個個檢查有無重覆嗎... 關於這個問題, 沒有完美的通解, 要看你的亂數值的範圍, 與你要產生的亂數個數來決定 1.假如你的值的範圍不大, 比如說撲克牌洗牌, 或從 0~幾十萬的數值範圍(m)裡取(n)個 不重複的亂數值, 最有效率的方法是陣列取值法, 虛擬碼如下 for(i in 0..m-1) e[i]=i; for(i in n-1..0) { r=亂數 0..i out(e[r]); e[r]=e[i]; } 它需要O(m)的儲存空間與O(n)的執行時間. 但因迴圈內每次的亂數範圍會變, 有些亂數產生器可能會有輸出不均勻問題. 假如你有足夠的記憶體空間, 且上面問題可以解決, 它是一個很好的選擇. 2.但假如你的值的範圍很大. 比如說要從 0~2^64 裡面選出1萬個不重複的數字, 方法1 就 有執行上的困難, 因為你難以找出那麼大的儲存空間 ( 記憶體 ), 那先取值然後檢查是 否已出現過就是比較可行的方案了, 虛擬碼如下 set<int64> oUsed; for(int i=0;i<10000;i++) { int64 r= 某亂數函數 if (!oUsed.insert(r).second) continue; out(r); } 當然用 hashset 通常會更快, 這裡只討論方法. 當然實際情況下, 問題可能介於兩者之間, 選擇就要評經驗與智慧了. -- Do not depend on others without effort... 當我年輕時,請教別人問題時常聽到上面那句話. 當時心裏偶而會有些小小抱怨. 當時間過去,我偶而會想到上面那句話, 心中十分感謝當初告訴我那句話的人. 當發現問題時,最有價值的不是問題的答案, 而是找到解決的方向,並在努力的過程裡具備解決問題的能力. --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 211.74.232.254