這兩天看到編程珠璣第二章，關于習題2.3中說到雜耍算法執行gcd（i,n）次后即可停止，這里我想了很久為什么？書中提到的Swap Sections解決了我的疑惑，在明白為什么的時候真的 “啊哈”了一下，原來這樣，感覺證明非常巧妙，不敢獨享，所以復述如下。 

　　problem:

　　rotate a one-dimensional vector of n elements left by i positions. For instance, with n=8 and i=3, the vector abcdefgh is rotated to defghabc.

　　這個問題可以有三個巧妙的算法來解決（關于這三個算法的代碼，我自己實現了一下，附在文后），這在Swap Sections都提到了，包括神奇的反轉算法、遞歸交換算法以及下面這個雜耍算法： 

　　one solution is:

　　move x[0] to the temporary t, then move x[i] to x[0], x[2i] to x[i], and so on, until we come back to taking an element from x[0], at which point we instead take the element from t and stop the process.

If that process didn't move all the elements , then we start over at x[1], and continue until we move all the elements.

　　這個算法在執行gcd（i,n）次后就停止了，為什么？ 先來了解一點數論知識（一下內容摘自《初等數論》，潘承洞著）： 

　　1 同余：

       設m不等于0, 若m|a-b,即 a-b=km, 則稱m為模，a同余于b模m，以及b是a對模m的剩余。記作<!--[if !msEquation]--> <!--[endif]-->。

　　2 同余類

       對給定的模m，有且恰有m個不同的模m的同余類，他們是

       0 mod m，1 mod m，…，（m-1）mod m。

　　3 完全剩余系

       一組數y1,y2,…，ys稱為是模m的完全剩余系，如果對任意的a有且僅有一個yj是a對模m的剩余，即a同余于yj模m。

       由此可見0,1,2，…，m-1是一個完全剩余系。因此，如果m個數是兩兩不同余的，那么這m個數便是完全剩余系。

　　基于以上知識，我們可以證明這樣一個事實，即如果i和n互質的話，那么序列：

       0     i mod n  2i mod n       3i mod n       ….   (n-1)*i mod n

　　就包括了集合{0,1,2 … n-1}的所有元素。（下一個元素(n)*i mod n 又是0）

　　為什么？

　　證明：

　　由于0,1,2，…，n-1本身是一個完全剩余系，即它們兩兩互不同余。設此序列為Xi（0<=i<=n-1），可得下式：

　　Xi≠Xj (mod n),   注：這里由于不能打出不同余字符因此用不等于替代

　　由于i與n是互質的，所以

　　Xi*i ≠i*Xj (mod n),這里由于不能打出不同余字符因此用不等于替代,因此i*Xi是m個互不同余數，那么可斷定它們是完全剩余系。有了上面的結論，那么如果i和n互質，下面的賦值過程便能完成所有值的賦值（設數組為X[0..n-1],長度為n）：

       t = X[0]

       X[0] = X[i mod n]

       X[i mod n] = X[2i mod n]

       …….

       X[(n-2)*i mod n] = X[(n-1)*i mod n]

       X[ (n-1)*i mod n] = t。

       因為以上操作已經把包括{0,1,…,n-1}所有元素放到了最終位置上，每次完成一個元素的放置。根據以上我們得到了一個中間結論，如果i和n互質，我們就可以一次完成。那么如果i和n不是互質的呢？ 自然的想法是利用我們已經得到的結論，讓i和n互質，即讓i’ = i/(gcd(i,n))，n’ = n/(gcd(i,n))。這樣便構造了一對互質的數, i’和n’。這意味著把整個數組的每g=gcd(i,n)個元素組成塊，如下所示：

       這樣，根據已得結論，我們可以一次獲得最終答案，因為i’和n’互質，由于我們的單位是塊元素，所以，必須要g次來完成塊的移動，每次相當于把g中的一個元素移到最終位置上。所以總共需要g次移動，算法終止。□ 整個證明過程最巧妙的地方在于對i和n進行處理的時候，以及處理之后轉換成塊元素的這個地方，感覺很巧妙，這樣的證明絕對秒殺什么陪集數目的說法，回味無窮。

　　三個算法的代碼：

1 /*
2 programming pearls: chapter2
3
4 Answer for Rotating a one-dimensional vector of n elements left by i positions.
5
6 method1: process 雜耍算法
7 method2: process2 交換算法
8 method3: process1 反轉算法
9 */
10
11 #include <iostream>
12
13 using namespace std;
14
15 const int num = 10;
16 int a[num] = {0,1,2,3,4,5,6,7,8,9};
17
18 //answer 1
19 /*
20 parameter 1: the vector to be rotated
21 par 2: the num of steps to rotate towards left
22 */
23
24 //assume m and n are not zero
25 int gcd(int m, int n)
26 {
27 while(m != n)
28 {
29 if(m > n)
30 m -= n;
31 else
32 n -= m;
33 }
34 return m;
35 }
36
37 //jungle code, method 1
38 void process(int* a, int i)
39 {
40 int n,m;
41 for(int j=0; j < gcd(i,num); j++)
42 {
43 n = a[j];
44 for(m=j+i; m!=j; m=(m+i)%num)
45 {
46 a[(m-i+num)%num] = a[m];
47 }
48 m = (m-i+num)%num;
49 a[m] = n;
50 }
51 }
52
53
54 void reverse(int m, int n)
55 {
56 int mid = (m+n)/2;
57 int temp;
58 // int j;
59
60 for(int i=m, j=n; i <= mid; i++,j--)
61 {
62 temp = a[i];
63 a[i] = a[j];
64 a[j] = temp;
65 }
66 }
67
68 //methond 3 反轉算法
69 void process1(int* a, int i)
70 {
71 reverse(0,i-1);
72 reverse(i,num-1);
73 reverse(0,num-1);
74 }
75
76
77 //method 2 交換算法
78 //swap a[i..i+m-1] with a[j..j+m-1]
79 void Swap(int*a, int i, int j, int m)
80 {
81 for(int l=0; l < m; l++)
82 {
83 int temp = a[i+l];
84 a[i+l] = a[j+l];
85 a[j+l] = temp;
86 }
87 }
88
89 //n remains the beginning of the rightmost section to be
90 // swapped. use variables i and j to denote the lengths of the
91 // sections still to be swapped.
92 //loop invariant:
93 // m n-i n n+j p-1
94 // |already swapped|swap with b[n..n+j-1]|swap with b[n-i..n-1]|already swapped|
95 void process2(int* a, int l)
96 {
97 if(l==0 || l==num)
98 {
99 return;
100 }
101
102 int n = l;
103 int j = num-l;
104 int i = l;
105 while(i != j)//當交換的兩邊長度相等時終止，最后再將相等的兩邊交換即可
106 {
107 if(i > j)
108 {
109 Swap(a,n-i,n,j);
110 i -= j;
111 }
112 else if(i < j)
113 {
114 Swap(a, n-i, n+j-i,i);
115 j -= i;
116 }
117 }
118 Swap(a,n-i,n,i);
119 }
120
121 int main()
122 {
123 process2(a,8);
124 //process1(a,9);
125
126 for(int i=0; i < num; i++)
127 cout<<a[i]<<" ";
128 cout<<endl;
129
130 int r;
131 cin>>r;
132 return 0;
133 }