作者ephesians (ephesians)
看板Programming
标题Re: [问题] array shuffle
时间Fri Jul 20 01:07:37 2007
※ 引述《xcycl (XOO)》之铭言：
: ※ 引述《[email protected] (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