算法合集之《置换群快速幂运算研究与探讨》

1置换群快速幂运算研究与探讨江苏省苏州中学潘震皓2基础知识群是集合G和定义在G上的二元运算符•组成的代数系统群满足封闭性、结合律、单位元和逆元基础知识置换置换T定义符号→，a被b取代=b=a→Ta(→)2T=a→T→T4213432114232431基础知识连接运算a→T1→T2=a→(T1•T2)1234432142134321134242134213432113424321基础知识循环2314526311246536543212133216543216543216543216置换群基本操作1.存储2.映射3.连接运算4.分解循环5.整幂运算6.开方运算O(n)O(1)O(n)O(n)?O(nlogk)?O(n+k)O(n+k)!!例题洗牌机(CEOI98)剀剀和凡凡有N张牌（依次标号为1，2，……，N）和一台洗牌机。假设N是奇数。洗牌机的功能是进行如下的操作：对所有位置I（1≤I≤N），如果位置I上的牌是J，而且位置J上的牌是K，那么通过洗牌机后位置I上的牌将是K。剀剀首先写下一个1~N的排列ai，在位置ai处放上数值ai+1的牌，得到的顺序x1,x2,...,xN作为初始顺序。他把这种顺序排列的牌放入洗牌机洗牌S次，得到牌的顺序为p1,p2,...,pN。现在，剀剀把牌的最后顺序和洗牌次数告诉凡凡，要凡凡猜出牌的最初顺序x1,x2,...,xN。例题位置i扑克牌j位置j扑克牌k位置i扑克牌kai位置ai扑克牌ai+1(1342)24134321位置牌一个引子设，（T为一循环，e为单位置换），那么k的最小正整数解为T的长度。eTkT=(135246)1265436543211265436543212T341265126543126543654321341265654321362451T=(135246)T2=(154)(263)T2是两个循环的乘积，这两个循环分别是循环T的奇数项和偶数项T=(135246)T3=(12)(34)(56)T3是三个循环的乘积，这三个循环分别是循环T中编号mod3=0,1,2的项当k|n时，Tk分裂成了k个循环的乘积，这k个循环分别是循环T中编号modk=0,1…k-1的项，按顺序的连接Ta*b=(Ta)ba=gcd(n,k)b=k/aTk=(Ta)b所以说，现在问题就转换到了长度n和指数k互质时的整幂运算。若，假设则：，显然，所以，令，naaaT...21nkbbbT...211iiaTa1ikibTbTTTbTbTbikiki...jiba1jkiba置换群整幂运算可以在线性时间复杂度内解决算法：–分解循环–从每个未扫描元素，按上述方法求得一个循环–将所有求得循环合并成置换开方运算开方运算比整幂运算复杂1.有多解2.有无解3.多解规律性不强需要解决的问题1.一个可行解2.解的个数T=(164)(235)T1=(146)(253)T2=(126345)T3=(136542)T12=T22=T32=T(164)(352)T=(1342)经过枚举，不存在一个T1满足T12=TT=(1342)(5768)T1=(15374628)，满足T12=T如果gcd(n,k)1，那么开方时就必须找k’个长度皆为n的循环合并(k’是gcd(n,k)的倍数，同时是k的因数)；否则，不能进行开方运算可行解生成的算法：–将置换分解成循环–对于每个可以不合并的循环，进行整幂运算的逆运算–对于必须合并的循环，每次选择gcd(n,k)个合并–将所得到的循环化为置换多解的产生1.合并与不合并之间2.选择几个循环合并3.选择哪几个循环合并4.合并时的“圆组合”T=(164)(235)T1=(146)(253)T2=(126345)T3=(136542)T12=T22=T32=T(164)(352)多解的产生1.合并与不合并之间2.选择几个循环合并3.选择哪几个循环合并4.合并时的“圆组合”例题单个循环，长度奇数指数是2的幂次总结置换群的幂运算这一问题是从最后一个例子洗牌机想到的，这一切都是对问题的深入研究带来的结果；分裂是自然而然的，而合并却是我们自己捏出来的，这一切又都是思想逆转所造成的结果；通过分裂和合并，置换群的幂运算被完美地解决了，这一切又都是多举例子多作猜想而得到的结果。每当发现问题，探寻问题，解决问题的时候，我们就会找到进步的道路。而完成这一切时，我们就进步了。谢谢大家排列矩阵(PermutationMatrix)–每行每列有且仅有一个元素值非零–此值为1–稀疏矩阵可以被表示为少量排列矩阵的和O(n3logk)=O(n+k)O(nm+km)