作者FRAXIS (喔喔)
看板Programming
标题Re: [问题] array shuffle
时间Fri Jul 20 09:01:06 2007
※ 引述《BaronDavis5 (Baron Davis)》之铭言：
: ※ 引述《ephesians (ephesians)》之铭言：
: 我也是用这个方法，主要idea是很久以前离散数学学过的一个permutation group
: 我猜应该是和前述cycle decomposition类似概念的东西
: 但是我之前把它写出来後，发现不同长度时，permutation group的量不一定
: 比如在元素长度8时，就存在二个permutation group (注1)
: 但是在长度20时，就只存在一个permutation group(皆扣掉头尾元素)
: 目前也想不出有没有什麽方法可以找出那些没交集permutation group...
以这题来说，在计算第i位置元素要被摆放的位置时，要考虑两种情况，
当i <= n时，元素要被放到 2i - 1 中
当i > n时，元素要被放到 2i % 2n中
不过麻烦的是，因为是一个cycle一个cycle去做，当检查到元素i时，
我没办法判断出这元素是已经到位了，还是没有到位。
除非元素本身有特性可以判断到位了没，又或是元素可以修改，不然
我想不到方法，这也就是困难之处。
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.119.162.51