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