[問題] 大數目的洗牌次數

看板C_and_CPP作者 (LS)時間12年前 (2013/10/20 13:45), 編輯推噓4(4推 0噓 7→)
留言11則, 6人參與, 最新討論串1/1
問題(Question)： 大數目的洗牌次數 當要產生的隨機數量n=10的時候， 我通常無腦大概跑個1000次(t)隨機交換應該就算洗得很乾淨了 當然假如只隨機交換1、2次，這樣不算完整的洗牌 我想請問這隨機交換的次數t與n的數目跟關係(即大約多少是比較合理的) 因為要跑的數值n可能很大(10W或100W)的情況， 我想較節省時間、又能達到較完整的隨機洗牌， 想詢問這t取多少是比較合理的 另外請問C++有什麼方便的函示庫可用嗎(雖然自己刻沒很難，但想長知識) 先感謝版友幫忙了 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 218.161.96.179
推
10/20 14:09, , 1F
你自己洗牌的時候覺得多少次合理 :P
10/20 14:09, 1F
推
10/20 14:14, , 2F
產生一個數字不重複的random數列再把排的順序對應過去
10/20 14:14, 2F
→
10/20 14:14, , 3F
比較省時間…
10/20 14:14, 3F
請問一下R大，洗牌的方法不就是產生一個數字不重複隨機數列的過程嗎? 因為我就是想生出個隨機數列來對應data，或著還有其他簡單快速的方法?
→
10/20 14:21, , 4F
10/20 14:21, 4F
→
10/20 14:30, , 5F
那篇文章你能參考，也可以在文章內搜尋 enough
10/20 14:30, 5F
→
10/20 14:30, , 6F
有討論到你的問題，基本上那就看你想要多亂
10/20 14:30, 6F
→
10/20 15:30, , 7F
感謝版友的幫助 謝謝
10/20 15:30, 7F
※ 編輯: Lsilver 來自: 218.161.96.179 (10/20 15:43)
推
10/20 16:11, , 8F
我所知洗牌法經過亂數均勻測試的是 Knuth Shuffle
10/20 16:11, 8F
推
10/20 17:18, , 9F
另外 <algorithm> 裡有 random_shuffle 可以用
10/20 17:18, 9F
→
10/20 17:19, , 10F
只要底層用的亂數是均勻的那它保證 n! 種排列的出現機率相同
10/20 17:19, 10F
→
10/20 17:23, , 11F
嘛, 常見的實作應該都是 Knuth shuffle 就是了
10/20 17:23, 11F
‣ 更多 Lsilver 的文章
文章代碼(AID): #1IOstyP6 (C_and_CPP)