资源描述：
《算法合集之《置换群快速幂运算 研究与探讨》》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、江苏省苏州中学潘震皓置换群快速幂运算研究与探讨江苏省苏州中学潘震皓[关键词]置换循环分裂合并[摘要]群是一个古老的数学分支，近几年来在程序设计中置换群得到了一定的应用。本文针对置换群的特点提出了线性时间的幂运算算法，并举例说明了优化后算法的效果。[正文]一、引言置换群是一种优秀的结构，在程序设计中，它的大部分基本操作，时间和空间复杂度都是线性的，甚至有的还是常数的。所以一个问题如果能够抽象归结为一个置换群模型的话，往往能够在程序设计中轻松地解决。但是对于整幂运算来说，似乎只能通过反复做乘法来获得O(k*乘法)或是O(
2、logk*乘法)的算法；而对于分数幂运算，则找不到较好的方法实现。二、置换群的整幂运算2.1整幂运算的一个转化在置换群中有一个定理：设，（T为一置换，e为单位置换（映射函数为的置换）），那么k的最小正整数解是T的拆分的所有循环长度的最小公倍数。或者有个更一般的结论：设，（T为一循环，e为单位置换），那么k的最小正整数解为T的长度。我们知道，单位置换就是若干个只含单个元素的循环的并。也就是说，长度为l的循环，l次的幂，把所有元素都完全分裂在这里，第一次出现了“分裂”。在后面的叙述中，将会多次出现。它的意思，通常是指将一
3、个循环按照modk的值平均地分成k个循环。了。这是为什么呢？我们来做一个试验：(下面的置换均以循环的连接表示)设n=6，那么。任取一T=(135246)，来做一遍乘法：分裂成了2份！而且这2份恰好是T的奇数项和偶数项！（注意可以写成(154)(326)）第11页共11页江苏省苏州中学潘震皓再来看看：不出所料，分裂成了3份，每份分别是在原来循环中的位置mod3=0,1,2的项。继续看：与前面不同的是，循环只分裂成了2份。并且每一份的循环看起来都是杂乱无章的，只知道是在循环中的奇数项和偶数项。再来拿做个试验：这次的循环，
4、根本没有分裂，只是顺序改变了一下。这之间有什么共同点呢？对，那就是gcd(k,l)。因为gcd(6,6)=6，所以循环会完全分裂，而gcd(2,6)=2,gcd(3,6)=3,gcd(4,6)=2,gcd(5,6)=1也相对应了上面的每一个试验的结果。第11页共11页江苏省苏州中学潘震皓经过多次试验以后，我们得到三个结论：结论一：一个长度为l的循环T，l是k的倍数，则是k个循环的乘积，每个循环分别是循环T中下标imodk=0,1,2…的元素按顺序的连接。结论二：一个长度为l的循环T，gcd(l,k)=1，则是一个循环
5、，与循环T不一定相同。结论三：一个长度为l的循环T，是gcd(l,k)个循环的乘积，每个循环分别是循环T中下标imodgcd(l,k)=0,1,2…的元素的连接。可以看出，结论三只不过是把k分成gcd(l,k)*(l/gcd(l,k))，再运用结论一和结论二所得到的。如果这几个结论是正确的话，那显然只需要确定结论二中叙述的，就能够在O(n)内解决任意循环的任意整幂运算了。2.2循环长度与指数互质时的整幂运算和上面一样，我们来做几个试验。设T=(12534)，则：不知大家有没有注意到，如果把循环T的奇数项和偶数项取出来
6、，就是154和23，如果两者并在一起，就是刚才求出的T2了。再试一个：同样地，把mod3=1,2,0的项取出来：13、24、5，连接在一起，就是所求得的新循环了。把这一试验结果写成一个定理，就是：设我们预先定义，若数组，则a按顺序包含了循环T，下标范围，且a[0]包含了循环中最小的元素，，且gcd(l,k)=1，则。第11页共11页江苏省苏州中学潘震皓这个定理看起来似乎挺复杂，但如果画张图看，一点也不复杂：设l=10,k=3：我们来一步一步构造Tk：第11页共11页江苏省苏州中学潘震皓像这样反复前进三格，然后涂色..
7、.最后，得到的循环就是所需要求的Tk了。证明：设任意，能唯一地找到，。那么j→T显然等于，(表示连续执行p次→T)由置换的连接的运算法则可知，。所以。由于循环的性质，我们令，就得到了上面的公式。2.3算法的实现根据上一节的定理和再上一节的3个结论，我们可以很方便地得到求整幂运算的O(n)算法，但是如果单纯地照着做，常数项是非常大的，有时甚至还不如O(nlogk)的算法快。针对这一问题，可以使用一个简化的算法：lFor源置换中每一个循环nFor环中每一个未标记元素uDol做上标记l放入结果数组l前进k格第11页共11页
8、江苏省苏州中学潘震皓uUntil回到这个元素u将结果数组中的元素取出，得到的环，便是目标置换包含的一个循环可以分析出，这个算法是符合上一节的定理和再上一节的3个结论的，在这里就不再说明了。循环的储存我们可以单纯地用2个数组来实现：一个是data，把每一个循环按顺序放在里面；一个是point，保存每个循环在data中的起始位置和长度。显然，2个数
