Re: [問題] array shuffle
※ 引述《xcycl (XOO)》之銘言：
: ※ 引述《foo.bbs@bbs.ntu.edu.tw (bar)》之銘言：
: : Method 3: tmp <- a <- b <- c <- d <- ...... <- alpha <- beta <- gama <- tmp
: : Similar to method 1, requiring a derived mathematical formula to
: : decide the next position to move.
: : Time complexity: n-1 moves (first and last elements being steady)
: : Space complexity: 1 element space for tmp
: 方法三可以說明一下嗎 ?
: 如果是將 permutation 做 cycle decomposition 時需要不止 O(1) 的空間,
: 還是有不作 cycle decomposition 的方法, 就可以算出來？
這方法蠻容易想到,但還不曉得該怎麼解釋,
具體來說:
要解決以下這個陣列的重排,
A1 = {1,3,5,7,9,2,4,6,8,10}
目的是排成這個樣子,
A2 = {1,2,3,4,5,6,7,8,9,10}
那粗淺一看,已確定1與10都排好了,而內部剩餘的數字應該做一連串的輪調動作,
2->3, (左邊意指某數字移動到右邊數字在A1所佔位置)
3->5,
5->9,
9->8,
8->6,
6->2,
4->7,
7->4.
以上輪調動作只是抄出來而已,我沒有指出其順序的意思.
想想交換二個變數的動作,或許可以延伸為三個變數的輪調,
例如:
S = {a,b,c}
輪調為
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若對任意長度原陣列可找到一個公式化的輪調順序,
結果就符合所求的時間與空間複雜度.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.160.213.154
討論串 (同標題文章)
Programming 近期熱門文章
PTT數位生活區 即時熱門文章
