作者BaronDavis5 (Baron Davis)
站內Programming
標題Re: [問題] array shuffle
時間Fri Jul 20 01:41:35 2007
※ 引述《ephesians (ephesians)》之銘言：
: ※ 引述《xcycl (XOO)》之銘言：
: S = {c,a,b}
: 則可以用
: swap(S[1],S[3]),swap(S[2],S[3])
: 或
: swap(S[2],S[3]),swap(S[1],S[2])
: 來做.
: 輪調三個變數要做二次,但只使用一個共用的temp變數.
: 同理,上述array shuffle若對任意長度原陣列可找到一個公式化的輪調順序,
: 結果就符合所求的時間與空間複雜度.
我也是用這個方法，主要idea是很久以前離散數學學過的一個permutation group
我猜應該是和前述cycle decomposition類似概念的東西
但是我之前把它寫出來後，發現不同長度時，permutation group的量不一定
比如在元素長度8時，就存在二個permutation group (註1)
但是在長度20時，就只存在一個permutation group(皆扣掉頭尾元素)
目前也想不出有沒有什麼方法可以找出那些沒交集permutation group...
(註1)
index 0 1 2 3 4 5 6 7
original 1 3 5 7 2 4 6 8
to 1 2 3 4 5 6 7 8
permutation group (1 2 4) (3 6 5)
(2 4 1),(6 5 3)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 59.115.233.21
1F：推 xcycl:是的, 算出 permutation 的 cycle 就是 220.134.69.245 07/20 02:13
2F：→ xcycl:cycle decomposition 220.134.69.245 07/20 02:14
※ 編輯: BaronDavis5 來自: 59.115.233.21 (07/20 04:04)