## 题目详情 有个长度为2n的数组{a1,a2,a3,...,an,b1,b2,b3,...,bn},希望排序后{a1,b1,a2,b2,....,an,bn},请考虑有无时间复杂度o(n),空间复杂度0(1)的解法。 **题目来源**:此题是去年2013年UC的校招笔试题,看似简单,按照题目所要排序后的字符串蛮力变化即可,但若要完美的达到题目所要求的时空复杂度,则需要我们花费不小的精力。OK,请看下文详解,一步步优化。 ## [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.09.md#分析与解法)分析与解法 ### [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.09.md#解法一蛮力变换)解法一、蛮力变换 题目要我们怎么变换,咱们就怎么变换。此题@陈利人也分析过,在此,引用他的思路进行说明。为了便于分析,我们取n=4,那么题目要求我们把 a1,a2,a3,a4,**b1,b2,b3,b4** 变成 a1,b1,a2,b2,a3,b3,a4,b4 #### [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.09.md#11步步前移)1.1、步步前移 仔细观察变换前后两个序列的特点,我们可做如下一系列操作: 第①步、确定b1的位置,即让b1跟它前面的a2,a3,a4交换: a1,b1,a2,a3,a4,**b2,b3,b4** 第②步、接着确定b2的位置,即让b2跟它前面的a3,a4交换: a1,b1,a2,b2,a3,a4,**b3,b4** 第③步、b3跟它前面的a4交换位置: a1,b1,a2,b2,a3,b3,a4,b4 b4已在最后的位置,不需要再交换。如此,经过上述3个步骤后,得到我们最后想要的序列。但此方法的时间复杂度为O(N^2),我们得继续寻找其它方法,看看有无办法能达到题目所预期的O(N)的时间复杂度。 #### [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.09.md#12中间交换)1.2、中间交换 当然,除了如上面所述的让b1,b2,b3,b4步步前移跟它们各自前面的元素进行交换外,我们还可以每次让序列中最中间的元素进行交换达到目的。还是用上面的例子,针对a1,a2,a3,a4,b1,b2,b3,b4 第①步:交换最中间的两个元素a4,b1,序列变成(待交换的元素用粗体表示): **a1,a2,a3**,b1,a4,**b2,b3,b4** 第②步,让最中间的两对元素各自交换: **a1,a2**,b1,a3,b2,a4,**b3,b4** 第③步,交换最中间的三对元素,序列变成: a1,b1,a2,b2,a3,b3,a4,b4 同样,此法同解法1.1、步步前移一样,时间复杂度依然为O(N^2),我们得下点力气了。 ### [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.09.md#解法二完美洗牌算法)解法二、完美洗牌算法 玩过扑克牌的朋友都知道,在一局完了之后洗牌,洗牌人会习惯性的把整副牌大致分为两半,两手各拿一半对着对着交叉洗牌,如下图所示: [![](http://box.kancloud.cn/2015-07-05_5598e1b12b842.jpg)](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/images/35/35.1.jpg) 如果这副牌用a1 a2 a3 a4 b1 b2 b3 b4表示(为简化问题,假设这副牌只有8张牌),然后一分为二之后,左手上的牌可能是a1 a2 a3 a4,右手上的牌是b1 b2 b3 b4,那么在如上图那样的洗牌之后,得到的牌就可能是b1 a1 b2 a2 b3 a3 b4 a4。 技术来源于生活,2004年,microsoft的Peiyush Jain在他发表一篇名为:“A Simple In-Place Algorithm for In-Shuffle”的论文中提出了完美洗牌算法。 这个算法解决一个什么问题呢?跟本题有什么联系呢? Yeah,顾名思义,完美洗牌算法解决的就是一个完美洗牌问题。什么是完美洗牌问题呢?即给定一个数组a1,a2,a3,...an,b1,b2,b3..bn,最终把它置换成b1,a1,b2,a2,...bn,an。读者可以看到,这个完美洗牌问题本质上与本题完全一致,只要在完美洗牌问题的基础上对它最后的序列swap两两相邻元素即可。 即: ~~~ a1,a2,a3,...an,b1,b2,b3..bn ~~~ 通过完美洗牌问题,得到: ~~~ b1,a1,b2,a2,b3,a3... bn,an ~~~ 再让上面相邻的元素两两swap,即可达到本题的要求: ~~~ a1,b1,a2,b2,a3,b3....,an,bn ~~~ 也就是说,如果我们能通过完美洗牌算法(时间复杂度O(N),空间复杂度O(1))解决了完美洗牌问题,也就间接解决了本题。 虽然网上已有不少文章对上篇论文或翻译或做解释说明,但对于初学者来说,理解难度实在太大,再者,若直接翻译原文,根本无法看出这个算法怎么一步步得来的,故下文将从完美洗牌算法的最基本的原型开始说起,以让读者能对此算法一目了然。 #### [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.09.md#21位置置换pefect_shuffle1算法)2.1、位置置换pefect_shuffle1算法 为方便讨论,我们设定数组的下标从1开始,下标范围是[1..2n]。 还是通过之前n=4的例子,来看下每个元素最终去了什么地方。 起始序列:a1 a2 a3 a4 b1 b2 b3 b4 数组下标:1 2 3 4 5 6 7 8 最终序列:b1 a1 b2 a2 b3 a3 b4 a4 从上面的例子我们能看到,前n个元素中, > 第1个元素a1到了原第2个元素a2的位置,即1->2; > > 第2个元素a2到了原第4个元素a4的位置,即2->4; > > 第3个元素a3到了原第6个元素b2的位置,即3->6; > > 第4个元素a4到了原第8个元素b4的位置,即4->8; 那么推广到一般情况即是:前n个元素中,第i个元素去了 第(2 * i)的位置。 上面是针对前n个元素,那么针对后n个元素,可以看出: > 第5个元素b1到了原第1个元素a1的位置,即5->1; > > 第6个元素b2到了原第3个元素a3的位置,即6->3; > > 第7个元素b3到了原第5个元素b1的位置,即7->5; > > 第8个元素b4到了原第7个元素b3的位置,即8->7; 推广到一般情况是,后n个元素,第i个元素去了第 (2 * (i - n) ) - 1 = 2 * i - (2 * n + 1) = (2 * i) % (2 * n + 1) 个位置。 再综合到任意情况,任意的第i个元素,我们最终换到了 (2 * i) % (2 * n + 1)的位置。为何呢?因为: > 当0 < i < n时, 原式= (2i) % (2 * n + 1) = 2i; > > 当i > n时,原式(2 * i) % (2 * n + 1)保持不变。 因此,如果题目允许我们再用一个数组的话,我们直接把每个元素放到该放得位置就好了。也就产生了最简单的方法pefect_shuffle1,参考代码如下: ~~~ // 时间O(n),空间O(n) 数组下标从1开始 void PefectShuffle1(int *a, int n) { int n2 = n * 2, i, b[N]; for (i = 1; i <= n2; ++i) { b[(i * 2) % (n2 + 1)] = a[i]; } for (i = 1; i <= n2; ++i) { a[i] = b[i]; } } ~~~ 但很明显,它的时间复杂度虽然是O(n),但其空间复杂度却是O(n),仍不符合本题所期待的时间O(n),空间O(1)。我们继续寻找更优的解法。 与此同时,我也提醒下读者,根据上面变换的节奏,我们可以看出有两个圈, > 一个是1 -> 2 -> 4 -> 8 -> 7 -> 5 -> 1; > > 一个是3 -> 6 -> 3。 下文2.2.1、走圈算法cycle_leader将再次提到这两个圈。 #### [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.09.md#22完美洗牌算法perfect_shuffle2)2.2、完美洗牌算法perfect_shuffle2 ##### [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.09.md#221走圈算法cycle_leader)2.2.1、走圈算法cycle_leader 因为之前perfect_shuffle1算法未达到时间复杂度O(N)并且空间复杂度O(1)的要求,所以我们必须得再找一种新的方法,以期能完美的解决本节开头提出的完美洗牌问题。 让我们先来回顾一下2.1节位置置换perfect_shuffle1算法,还记得我之前提醒读者的关于当n=4时,通过位置置换让每一个元素到了最后的位置时,所形成的两个圈么?我引用下2.1节的相关内容: 当n=4的情况: 起始序列:a1 a2 a3 a4 b1 b2 b3 b4 数组下标:1 2 3 4 5 6 7 8 最终序列:b1 a1 b2 a2 b3 a3 b4 a4 即通过置换,我们得到如下结论: “于此同时,我也提醒下读者,根据上面变换的节奏,我们可以看出有两个圈, > 一个是1 -> 2 -> 4 -> 8 -> 7 -> 5 -> 1; > > 一个是3 -> 6 -> 3。” 这两个圈可以表示为(1,2,4,8,7,5)和(3,6),且perfect_shuffle1算法也已经告诉了我们,不管你n是奇数还是偶数,每个位置的元素都将变为第(2*i) % (2n+1)个元素: 因此我们只要知道圈里最小位置编号的元素即圈的头部,顺着圈走一遍就可以达到目的,且因为圈与圈是不相交的,所以这样下来,我们刚好走了O(N)步。 还是举n=4的例子,且假定我们已经知道第一个圈和第二个圈的前提下,要让1 2 3 4 5 6 7 8变换成5 1 6 2 7 3 8 4: 第一个圈:1 -> 2 -> 4 -> 8 -> 7 -> 5 -> 1 第二个圈:3 -> 6 -> 3: 原始数组:1 2 3 4 5 6 7 8 数组下标:1 2 3 4 5 6 7 8 走第一圈:5 1 3 2 7 6 8 4 走第二圈:5 1 6 2 7 3 8 4 上面沿着圈走的算法我们给它取名为cycle_leader,这部分代码如下: ~~~ //数组下标从1开始,from是圈的头部,mod是要取模的数 mod 应该为 2 * n + 1,时间复杂度O(圈长) void CycleLeader(int *a, int from, int mod) { int t,i; for (i = from * 2 % mod; i != from; i = i * 2 % mod) { t = a[i]; a[i] = a[from]; a[from] = t; } } ~~~ ##### [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.09.md#222神级结论若2n3k---1则可确定圈的个数及各自头部的起始位置)2.2.2、神级结论:若2*n=(3^k - 1),则可确定圈的个数及各自头部的起始位置 下面我要引用此论文“A Simple In-Place Algorithm for In-Shuffle”的一个结论了,即 对于2*n = (3^k-1)这种长度的数组,恰好只有k个圈,且每个圈头部的起始位置分别是1,3,9,...3^(k-1)。 论文原文部分为: [![](http://box.kancloud.cn/2015-07-05_5598e1c513b46.jpg)](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/images/35/35.2.jpg) 也就是说,利用上述这个结论,我们可以解决这种特殊长度2*n = (3^k-1)的数组问题,那么若给定的长度n是任意的咋办呢?此时,我们可以采取分而治之算法的思想,把整个数组一分为二,即拆分成两个部分: 让一部分的长度满足神级结论:若2*m = (3^k-1),则恰好k个圈,且每个圈头部的起始位置分别是1,3,9,...3^(k-1)。其中m < n,m往神级结论所需的值上套; 剩下的n-m部分单独计算; 当把n分解成m和n-m两部分后,原始数组对应的下标如下(为了方便描述,我们依然只需要看数组下标就够了): 原始数组下标:1..m m+1.. n, n+1 .. n+m, n+m+1,..2*n 且为了能让前部分的序列满足神级结论2*m = (3^k-1),我们可以把中间那两段长度为n-m和m的段交换位置,即相当于把m+1..n,n+1..n+m的段循环右移m次(为什么要这么做?因为如此操作后,数组的前部分的长度为2m,而根据神级结论:当2m=3^k-1时,可知这长度2m的部分恰好有k个圈)。 而如果读者看过本系列第一章、左旋转字符串的话,就应该意识到循环位移是有O(N)的算法的,其思想即是把前n-m个元素(m+1.. n)和后m个元素(n+1 .. n+m)先各自翻转一下,再将整个段(m+1.. n, n+1 .. n+m)翻转下。 这个翻转的代码如下: ~~~ //翻转字符串时间复杂度O(to - from) void reverse(int *a, int from, int to) { int t; for (; from < to; ++from, --to) { t = a[from]; a[from] = a[to]; a[to] = t; } } //循环右移num位 时间复杂度O(n) void RightRotate(int *a, int num, int n) { reverse(a, 1, n - num); reverse(a, n - num + 1, n); reverse(a, 1, n); } ~~~ 翻转后,得到的目标数组的下标为: ~~~ 目标数组下标:1..m n+1..n+m m+1 .. n n+m+1,..2*n ~~~ OK,理论讲清楚了,再举个例子便会更加一目了然。当给定n=7时,若要满足神级结论2*n=3^k-1,k只能取2,继而推得n‘=m=4。 ~~~ 原始数组:a1 a2 a3 a4 a5 a6 a7 b1 b2 b3 b4 b5 b6 b7 ~~~ 既然m=4,即让上述数组中有下划线的两个部分交换,得到: ~~~ 目标数组:a1 a2 a3 a4 b1 b2 b3 b4 a5 a6 a7 b5 b6 b7 ~~~ 继而目标数组中的前半部分a1 a2 a3 a4 b1 b2 b3 b4部分可以用2.2.1、走圈算法cycle_leader搞定,于此我们最终求解的n长度变成了n’=3,即n的长度减小了4,单独再解决后半部分a5 a6 a7 b5 b6 b7即可。 ##### [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.09.md#223完美洗牌算法perfect_shuffle3)2.2.3、完美洗牌算法perfect_shuffle3 从上文的分析过程中也就得出了我们的完美洗牌算法,其算法流程为: > 输入数组 A[1..2 * n] > > step 1 找到 2 * m = 3^k - 1 使得 3^k <= 2 * n < 3^(k +1) > > step 2 把a[m + 1..n + m]那部分循环移m位 > > step 3 对每个i = 0,1,2..k - 1,3^i是个圈的头部,做cycle_leader算法,数组长度为m,所以对2 * m + 1取模。 > > step 4 对数组的后面部分A[2 * m + 1.. 2 * n]继续使用本算法, 这相当于n减小了m。 上述算法流程对应的论文原文为: 以上各个步骤对应的时间复杂度分析如下: > 因为循环不断乘3的,所以时间复杂度O(logn) > > 循环移位O(n) > > 每个圈,每个元素只走了一次,一共2*m个元素,所以复杂度omega(m), 而m < n,所以 也在O(n)内。 T(n - m) > > 因此总的时间复杂度为 T(n) = T(n - m) + O(n) ,m = omega(n) ,解得:T(n) = O(n)。 此完美洗牌算法实现的参考代码如下: ~~~ //copyright@caopengcs 8/24/2013 //时间O(n),空间O(1) void PerfectShuffle2(int *a, int n) { int n2, m, i, k, t; for (; n > 1;) { // step 1 n2 = n * 2; for (k = 0, m = 1; n2 / m >= 3; ++k, m *= 3) ; m /= 2; // 2m = 3^k - 1 , 3^k <= 2n < 3^(k + 1) // step 2 right_rotate(a + m, m, n); // step 3 for (i = 0, t = 1; i < k; ++i, t *= 3) { cycle_leader(a , t, m * 2 + 1); } //step 4 a += m * 2; n -= m; } // n = 1 t = a[1]; a[1] = a[2]; a[2] = t; } ~~~ ##### [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.09.md#224perfect_shuffle2算法解决其变形问题)2.2.4、perfect_shuffle2算法解决其变形问题 啊哈!以上代码即解决了完美洗牌问题,那么针对本章要解决的其变形问题呢?是的,如本章开头所说,在完美洗牌问题的基础上对它最后的序列swap两两相邻元素即可,代码如下: ~~~ //copyright@caopengcs 8/24/2013 //时间复杂度O(n),空间复杂度O(1),数组下标从1开始,调用perfect_shuffle3 void shuffle(int *a, int n) { int i, t, n2 = n * 2; PerfectShuffle2(a, n); for (i = 2; i <= n2; i += 2) { t = a[i - 1]; a[i - 1] = a[i]; a[i] = t; } } ~~~ 上述的这个“在完美洗牌问题的基础上对它最后的序列swap两两相邻元素”的操作(当然,你也可以让原数组第一个和最后一个不变,中间的2 * (n - 1)项用原始的标准完美洗牌算法做),只是在完美洗牌问题时间复杂度O(N)空间复杂度O(1)的基础上再增加O(N)的时间复杂度,故总的时间复杂度O(N)不变,且理所当然的保持了空间复杂度O(1)。至此,咱们的问题得到了圆满解决! ## [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.09.md#问题扩展)问题扩展 ### [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.09.md#神级结论是如何来的)神级结论是如何来的? 我们的问题得到了解决,但本章尚未完,即决定完美洗牌算法的神级结论:若2*n=(3^k - 1),则恰好只有k个圈,且每个圈头部的起始位置分别是1,3,9,...3^(k-1),是如何来的呢? [![](http://box.kancloud.cn/2015-07-05_5598e1d9474e4.jpg)](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/images/35/35.3.jpg) 要证明这个结论的关键就是:这所有的圈合并起来必须包含从1到M之间的所有正数,一个都不能少。这个证明有点麻烦,因为证明过程中会涉及到群论等数论知识,但再远的路一步步走也能到达。 首先,让咱们明确以下相关的概念,定理,及定义(搞清楚了这些东西,咱们便证明了一大半): > 概念1 mod表示对一个数取余数,比如3 mod 5 =3,5 mod 3 =2; > > 定义1 欧拉函数ϕ(m) 表示为不超过m(即小于等于m)的数中,与m互素的正整数个数 > > 定义2 若ϕ(m)=Ordm(a) 则称a为m的原根,其中Ordm(a)定义为:a ^d ( mod m),其中d=0,1,2,3…,但取让等式成立的最小的那个d。 结合上述定义1、定义2可知,2是3的原根,因为2^0 mod 3 = 1, 2^1 mod 3 = 2, 2^2 mod 3 = 1, 2^3 mod 3 = 2,{a^0 mod m,a^1 mod m,a^2}得到集合S={1,2},包含了所有和3互质的数,也即d=ϕ(2)=2,满足原根定义。 而2不是7的原根,这是因为2^0 mod 7 = 1, 2^1 mod 7 = 2, 2^2 mod 7 = 4, 2^3 mod 7 = 1,2^4 mod 7 = 2,2^5 mod 7 = 4,2^6 mod 7 = 1,从而集合S={1,2,4}中始终只有1、2、4三种结果,而没包含全部与7互质的数(3、6、5便不包括),,即d=3,但ϕ(7)=6,从而d != ϕ(7),不满足原根定义。 再者,如果说一个数a,是另外一个数m的原根,代表集合S = {a^0 mod m, a^1 mod m, a^2 mod m…… },得到的集合包含了所有小于m并且与m互质的数,否则a便不是m的原根。而且集合S = {a^0 mod m, a^1 mod m, a^2 mod m…… }中可能会存在重复的余数,但当a与m互质的时候,得到的{a^0 mod m, a^1 mod m, a^2 mod m}集合中,保证了第一个数是a^0 mod m,故第一次发现重复的数时,这个重复的数一定是1,也就是说,出现余数循环一定是从开头开始循环的。 > 定义3 对模指数,a对模m的原根定义为 [![](http://box.kancloud.cn/2015-07-05_5598e1e90c863.jpg)](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/images/35/35.4.jpg),st:[![](http://box.kancloud.cn/2015-07-05_5598e1f855c6a.jpg)](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/images/35/35.5.jpg)中最小的正整数d 再比如,2是9的原根,因为[![](http://box.kancloud.cn/2015-07-05_5598e203366d4.jpg)](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/images/35/35.6.jpg),为了让[![](http://box.kancloud.cn/2015-07-05_5598e2103e6d1.jpg)](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/images/35/35.7.jpg)除以9的余数恒等于1,可知最小的正整数d=6,而ϕ(m)=6,满足原根的定义。 > 定理1 同余定理:两个整数a,b,若它们除以正整数m所得的余数相等,则称a,b对于模m同余,记作[![](http://box.kancloud.cn/2015-07-05_5598e21d1b2a5.jpg)](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/images/35/35.8.jpg),读做a与b关于模m同余。 > > 定理2 当p为奇素数且a是[![](http://box.kancloud.cn/2015-07-05_5598e224ce806.jpg)](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/images/35/35.9.jpg)的原根时⇒ a也是[![](http://box.kancloud.cn/2015-07-05_5598e229aa80e.jpg)](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/images/35/35.10.jpg)的原根 > > 定理3 费马小定理:如果a和m互质,那么a^ϕ(m) mod m = 1 > > 定理4 若(a,m)=1 且a为m的原根,那么a是(Z/mZ)*的生成元。 取a = 2, m = 3。 我们知道2是3的原根,2是9的原根,我们定义S(k)表示上述的集合S,并且取x = 3^k(x表示为集合S中的数)。 所以: ~~~ S(1) = {1, 2} S(2) = {1, 2, 4, 8, 7, 5} ~~~ 我们没改变圈元素的顺序,由前面的结论S(k)恰好是一个圈里的元素,且认为从1开始循环的,也就是说从1开始的圈包含了所有与3^k互质的数。 那与3^k不互质的数怎么办?如果0 < i < 3^k与 3^k不互质,那么i 与3^k的最大公约数一定是3^t的形式(只包含约数3),并且 t < k。即gcd(i , 3^k) = 3^t,等式两边除以个3 ^ t,即得gcd( i/(3^t),3^(k - t) ) = 1, i/(3^t) 都与3^(k - t) 互质了,并且i / (3^t) < 3^(k - t), 根据S(k)的定义,可见i/(3^t) 在集合S(k - t)中。 同理,任意S(k - t)中的数x,都满足gcd(x , 3^k) = 1,于是gcd(3^k , x* 3^t) = 3 ^ t, 并且x_3^t < 3^k。可见S(k - t)中的数x_3^t 与 i形成了一一对应的关系。 也就是说S(k - t)里每个数x* 3^t形成的新集合包含了所有与3^k的最大公约数为3^t的数,它也是一个圈,原先圈的头部是1,这个圈的头部是3^t。 于是,对所有的小于 3^k的数,根据它和3^k的最大公约数,我们都把它分配到了一个圈里去了,且k个圈包含了所有的小于3^k的数。 下面,举个例子,如caopengcs所说,当我们取“a = 2, m = 3时, 我们知道2是3的原根,2是9的原根,我们定义S(k)表示上述的集合S,并且x= 3^k。 所以S(1) = {1, 2} S(2) = {1, 2, 4, 8, 7, 5} 比如k = 3。 我们有: S(3) = {1, 2 ,4 , 8, 16, 5, 10, 20, 13, 26, 25, 23, 19, 11, 22, 17, 7, 14} 包含了小于27且与27互质的所有数,圈的首部为1,这是原根定义决定的。 那么与27最大公约数为3的数,我们用S(2)中的数乘以3得到。 S(2) * 3 = {3, 6, 12, 24, 21, 15}, 圈中元素的顺序没变化,圈的首部是3。 与27最大公约数为9的数,我们用S(1)中的数乘以9得到。 S(1) * 9 = {9, 18}, 圈中得元素的顺序没变化,圈的首部是9。 因为每个小于27的数和27的最大公约数只有1, 3, 9这3种情况,又由于前面所证的一一对应的关系,所以S(2) * 3包含了所有小于27且与27的最大公约数为3的数,S(1) * 9 包含了所有小于27且和27的最大公约数为9的数。” 换言之,若定义为整数,假设/N定义为整数Z除以N后全部余数的集合,包括{0...N-1}等N个数,而(/N)*则定义为这Z/N中{0...N-1}这N个余数内与N互质的数集合。 则当n=13时,2n+1=27,即得/N ={0,1,2,3,.....,26},(/N)*相当于就是{0,1,2,3,.....,26}中全部与27互素的数的集合; 而2^k(mod 27)可以把(/27)*取遍,故可得这些数分别在以下3个圈内: 取头为1,(/27)*={1,2,4,8,16,5,10,20,13,26,25,23,19,11,22,17,7,14},也就是说,与27互素且小于27的正整数集合为{1,2,4,8,16,5,10,20,13,26,25,23,19,11,22,17,7,14},因此ϕ(m) = ϕ(27)=18, 从而满足[![](http://box.kancloud.cn/2015-07-05_5598e230c0780.jpg)](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/images/35/35.11.jpg)的最小d = 18,故得出2为27的原根; 取头为3,就可以得到{3,6,12,24,21,15},这就是以3为头的环,这个圈的特点是所有的数都是3的倍数,且都不是9的倍数。为什么呢?因为2^k和27互素。 具体点则是:如果3×2^k除27的余数能够被9整除,则有一个n使得3_2^k=9n(mod 27),即3_2^k-9n能够被27整除,从而3*2^k-9n=27m,其中n,m为整数,这样一来,式子约掉一个3,我们便能得到2^k=9m+3n,也就是说,2^k是3的倍数,这与2^k与27互素是矛盾的,所以,3×2^k除27的余数不可能被9整除。 此外,2^k除以27的余数可以是3的倍数以外的所有数,所以,2^k除以27的余数可以为1,2,4,5,7,8,当余数为1时,即存在一个k使得2^k-1=27m,m为整数。 式子两边同时乘以3得到:3_2^k-3=81m是27的倍数,从而3_2^k除以27的余数为3; 同理,当余数为2时,2^k - 2 = 27m,=> 3_2^k- 6 =81m,从而3_2^k除以27的余数为6; 当余数为4时,2^k - 4 = 37m,=> 3_2^k - 12 =81m,从而3_2^k除以27的余数为12; 同理,可以取到15,21,24。从而也就印证了上面的结论:取头为3,就可以得到{3,6,12,24,21,15}。 取9为头,这就很简单了,这个圈就是{9,18} 你会发现,小于27的所有自然数,要么在第一个圈里面,也就是那些和27互素的数;要么在第二个圈里面,也就是那些是3的倍数,但不是9的倍数的数;要么在第三个圈里面,也就是是9倍数的数,而之所以能够这么做,就是因为2是27的本原根。证明完毕。 最后,咱们也再验证下上述过程: 因为[![](http://box.kancloud.cn/2015-07-05_5598e2340276c.jpg)](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/images/35/35.12.jpg),故: i = 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 由于n=13,2n+1 = 27,据此[![](http://box.kancloud.cn/2015-07-05_5598e237440ef.jpg)](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/images/35/35.13.jpg)公式可知,上面第 i 位置的数将分别变成下述位置的: i = 2 4 6 8 10 12 14 16 18 20 22 24 26 1 3 5 7 9 11 13 15 17 19 21 23 25 0 根据i 和 i‘ 前后位置的变动,我们将得到3个圈: ~~~ 1->2->4->8->16->5->10->20->13->26->25->23->19->11->22->17->7->14->1; 3->6->12->24->21->15->3 9->18->9 ~~~ 没错,这3个圈的数字与咱们之前得到的3个圈一致吻合,验证完毕。 ## [](https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/02.09.md#举一反三)举一反三 至此,本章开头提出的问题解决了,完美洗牌算法的证明也证完了,是否可以止步了呢?OH,NO!读者有无思考过下述问题: 1、既然完美洗牌问题是给定输入:a1,a2,a3,……aN,b1,b2,b3,……bN,要求输出:b1,a1,b2,a2,……bN,aN;那么有无考虑过它的逆问题:即给定b1,a1,b2,a2,……bN,aN,,要求输出a1,a2,a3,……aN,b1,b2,b3,……bN ? 2、完美洗牌问题是两手洗牌,假设有三只手同时洗牌呢?那么问题将变成:输入是a1,a2,……aN, b1,b2,……bN, c1,c2,……cN,要求输出是c1,b1,a1,c2,b2,a2,……cN,bN,aN,这个时候,怎么处理?