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

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