作者ephesians (ephesians)
看板Programming
标题Re: [问题] array shuffle
时间Fri Jul 20 02:58:56 2007
※ 引述《BaronDavis5 (Baron Davis)》之铭言：
: 我也是用这个方法，主要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)
我的想法不很像,而且稍有些降级,是O(n^2)时间复杂度.
{1,3,5,7;2,4,6,8}
这个阵列,如果我先将最外围未正确归定位的数字做对,就是
3 _ _
{1,2,5,7;2,4,7,8}
6
意思是阵列中存在着左边{3,5,7}与右边{2,4,6}子阵列,右子阵列的头要变成
左边的头,左子阵列的尾要变成右边的尾;因此,2将3挤掉,7将6挤掉.
接着问题是,挤出来的3,6该摆在哪里呢? 分别摆在原来的2,7位置吗?
若程式这样写的话,得到的结果只是一个很接近答案的阵列,里头仍有部份凌乱.
但如果以更小步骤来想,挤出来的3应该把右边的5往右边挤过去,
挤出来的6则应该把左边的4往左边挤过去,
如果真把这推挤动作编入演算法中,时间就是O(n^2)复杂度.
其实这想法来自於较高阶的想法,像俄罗斯娃娃那样一层一层处理. 像以下阵列
{1,3,5,7,9,11;2,4,6,8,10,12}
先对调第一层子阵列,
{1,[2,4,6,8,10];[3,5,7,9,11],12}
再对调第二层子阵列,
{1,2,[3,5,7,9];[4,6,8,10],11,12}
再对调第三层子阵列,
{1,2,3,[4,6,8];[5,7,9],10,11,12}
如此做下去,一定能得到答案.
但这做法是O(n^2).
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 218.160.213.154