作者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)