学步园

  向量旋转问题： 给定一个 n 维向量， 求 将它向左循环移动 i 位后的向量。比如： [1,2,3,4,5] 向左循环移动 3 位后，变成 [4,5,1,2,3] 。为了简单起见，向量采用数组表示。

           本文讨论的内容参见《编程珠玑 I 》 ( 第二版 ) 的第二章。在那里，讨论了向量旋转的四种算法：

           1. 基于数组移动的思路： 这个是比较简单的， 即将要移动的 i 个元素复制到一个临时数组中，然后，将原数组的 n-i 个元素依次复制到前 n-i 个位置上，最后，将临时数组中的 i 个元素移动到原数组的末尾 i 个位置上。该思路实现简单，运行时间效率为 O(n) , 空间效率是 O(i) ；当 i 较大时，会有较大的空间消耗。

           图示： [1,2,3,4,5] ---> [4,5,3,4,5] ---> [4,5,1,2,3]

                                       |---> 临时数组： [1,2,3] -------- >|⇑

           2. 基于跳跃交换元素的思路：

       实际上，也是比较直观的。 例如， [1,2,3,4,5] ， I = 3. 直观的想法， 4 肯定要到 1 的位置上； 那么谁到 4 的位置上呢？ 这需要将数组想像成一个环形（类似循环队列），在逻辑上通常是取模操作。 [1,2,3,4,5,1,2,3,4,5] ，显然， 2 到 4 的位置。 2 = (4+3) % 5. 接着， 5 到 2 的位置； (5+3) % 5 = 3 到 5 的位置；(3+3) % 5 = 1 到 3 的位置。这样形成了一个跳跃链： [1<4<2<5<3<1]

      即： arr[1] = arr[4] ; arr[4] = arr[2]; arr[2] = arr[5]; arr[5] = arr[3]; arr[3] = arr[1]. 这样跳跃交换后，得到最终结果： [4,5,1,2,3]

          当 n 与 I 具有大于 1 的最大公约数时，情形略有所不同。 例如， [1,2,3,4,5,6] , I = 4. 需要分两轮( 轮数是 n 与 i 的最大公约数 ):

          S1: arr[1] = arr[5] , arr[5] = arr[3], arr[3] = arr[1] ,

          S2: arr[2] = arr[6], arr[6] = arr[4], arr[4] = arr[2].

      至此，也得到最终结果： [5,6,1,2,3,4]

           后面两种思路基于同一个观察结果： 向量旋转实际上就是将 AB 转换为 BA 的过程。

           3. 基于数组区域交换的思路： AB ---> BA

           (1) 若 A 与 B 长度相等，则将数组区域 A 和 B 交换即可；

           (2) 若 A 的长度小于 B ，则将 B 分成两部分 BlBr 其中 Br 的长度与 A 相等。则 AB = ABlBr. 交换数组区域 A 与 Br , 得到 BrBlA ，此时， A 已经在最终位置。问题转换为： 将向量 BrBl 左移  length(Br) 位；即原问题的更小规模形式，可递归求解；

           (3) 若 A 的长度大于 B ，则将 A 分成两部分 AlAr ，其中， Al 的长度与 B 相等。则 AB = AlArB. 交换数组区域 Al 与 B ，得到 BArAl ，此时， B 已经在最终位置上，问题转换为：将向量 ArAl 左移  length(Ar)位；即原问题的更小规模形式，可递归求解。

           图示： [1 2 3 4 5 6 7 8 9 10] ,  n=10, I = 3 ;  

           S1: A=[1,2,3] , B=[4,5,6,7,8,9] ; A < B.

           根据 (2) ---> [1 2 3 | 4 5 6 7 | 8 9 10] --->    [8 9 10 | 4 5 6 7 | 1 2 3]

       n = 7, I = 3; [1 2 3] 已在最终位置；

           第一趟结果 ： [ 8 9 10 4 5 6 7 * 1 2 3] ; n = 7; I = 3

            S2: A = [8,9,10] , B= [4,5,6,7] ; A < B

            根据 (2) ---> [8 9 10 | 4 | 5 6 7] ---> [5 6 7 | 4 | 8 9 10]

             n = 4, I = 3; [8,9,10] 已在最终位置；

            第二趟结果： [ 5 6 7 4 * 8 9 10 1 2 3] ; n = 4, I = 3

            S3: A=[5,6,7] , B = [4] ; A > B

            根据 (3) ---> [5 | 6,7 | 4] ---> [4 | 6,7 | 5]

       n = 3, i = 2 ; [4] 已在最终位置。

           第三趟结果： [4 * 6 7 5 * 8 9 10 1 2 3] ; n = 3, I = 2

             S4: A=[6,7] , B= [5] ; A > B

            根据 (3) ---> [6 | 7 | 5] ---> [5 | 7 | 6]

        n = 2, I = 1; [5] 已在最终位置

             第四趟结果： [4 5 * 7 6 * 8 9 10 1 2 3] ; n = 2, I = 1

             S5: A= [7] , B= [6] ; A=B

             根据 (1) ---> [6,7] 算法结束。至此所有元素都在其位置上。

             第五趟结果： [4 5 6 7 8 9 10 1 2 3]

           4. 基于数组逆置的思路： 一个非常优雅而简单的公式： (a^r b^r )^r = ba ，类似于对偶律，可用数学归纳法证明。这意味着，只要将 a 部分逆置，然后将 b 部分逆置，最后将整个部分逆置，就得到了所期望的结果。算法简单，优雅，并且高效，不易出错；时间效率是 O(n) ，空间效率是 O(1) 。这说明，掌握一定的计算机科学知识和方法对于程序设计是非常重要的。

            图示： [1,2,3,4,5] ---> [3,2,1,4,5] ---> [3,2,1,5,4] ---> [4,5,1,2,3]

1. /** 
2.  * VectorRotation  @author shuqin1984 2011-04-18 
3.  *  
4.  * 本程序主要实现四种向量旋转算法;  
5.  * 向量旋转问题： 将给定 n 维向量最左边的 i 位依次移动到向量最右边. 
6.  * 比如，[1,2,3,4,5] 左移 3 位， 变成 [4,5,1,2,3] 
7.  * 数据结构与算法描述 
8.  * 1. 向量使用数组来表示； 
9.  * 2. 四种算法如前所述，分别基于"移动数组元素", "跳跃交换元素", "交换数组区域", "数组逆置" 四种思路。 
10.  */  
11. package algorithm.vector;  
12. import java.util.Arrays;  
13. public class VectorRotation {  
14.       
15.     private VectorRotation() { }  
16.       
17.     /** 
18.      * leftShift4: 基于移动数组元素的思路实现向量旋转. 
19.      */  
20.     public static int[] leftShift4(int[] arr, int i)  
21.     {  
22.         int shiftBits = processParameters(arr, i);        
23.         if (shiftBits == 0) {  
24.             return arr;  
25.         }  
26.           
27.         int arrlen = arr.length;  
28.         int[] temp = new int[shiftBits];  
29.         for (int k=0; k < shiftBits; k++) {  
30.             temp[k] = arr[k];  
31.         }  
32.         for (int k=shiftBits; k < arrlen; k++) {  
33.             arr[k-shiftBits] = arr[k];  
34.         }  
35.         for (int k = 0; k < shiftBits; k++) {  
36.             arr[k + arrlen-shiftBits] = temp[k];  
37.         }  
38.         return arr;  
39.     }  
40.       
41.     /** 
42.      * leftShift3 : 基于跳跃交换元素求解向量旋转问题 
43.      */  
44.     public static int[] leftShift3(int[] arr, int i)  
45.     {  
46.         int shiftBits = processParameters(arr, i);  
47.         if (shiftBits == 0) {  
48.             return arr;  
49.         }  
50.         int arrlen = arr.length;  
51.         for (int k=0; k < gcd(arr.length, shiftBits); k++) {    
52.             int temp = arr[k];  
53.             int foreIndex = k;  
54.             int afterIndex = k + shiftBits;  
55.             while (afterIndex != k) {  
56.                 arr[foreIndex] = arr[afterIndex];  
57.                 foreIndex = (foreIndex + shiftBits) % arrlen;   
58.                 afterIndex = (afterIndex + shiftBits) % arrlen;  
59.             }  
60.             arr[foreIndex] = temp;  
61.         }  
62.         return arr;  
63.     }  
64.       
65.     /* 
66.      * gcd: 求给定两数的最大公约数 
67.      */  
68.     private static int gcd(int m, int n)  
69.     {  
70.         if (m < 0 || n < 0) {  
71.             throw new IllegalArgumentException("参数错误，必须均是正整数!");  
72.         }  
73.         if (m % n == 0) {  
74.             return n;  
75.         }   
76.         return gcd(n, m%n);  
77.     }  
78.       
79.     /** 
80.      * leftShift2 : 基于交换数组区域求解向量旋转问题 
81.      */  
82.     public static int[] leftShift2(int[] arr, int i)   
83.     {  
84.         int shiftBits = processParameters(arr, i);  
85.         if (shiftBits == 0) {  
86.             return arr;  
87.         }  
88.         int beginIndex = 0;  
89.         int endIndex = arr.length-1;  
90.         int varlength = endIndex - beginIndex + 1;  
91.         while (true) {    
92.             if (varlength == 2 * shiftBits) {  // AB -> BA ; 所要左移的位数正好是数组长度的一半，只要将数组左右等长区域交换即可  
93.                 exchange(arr, beginIndex, beginIndex + shiftBits, shiftBits);  
94.                 break;  
95.             } else if (varlength > 2 * shiftBits) { // ABlBr -> BrBlA ; 所要左移的位数小于数组长度的一半，将右边区域分成两份，并将其右半部分与左边区域交换  
96.                 exchange(arr, beginIndex, varlength-shiftBits, shiftBits);  
97.                 endIndex -= shiftBits;  
98.             } else if (varlength < 2 * shiftBits) { // AlArB -> BArAl ; 所要左移的位数大于数组长度的一半，将左边区域分成两份，并将其左半部分与右边区域交换  
99.                 exchange(arr, beginIndex, beginIndex + shiftBits, varlength - shiftBits);  
100.                 beginIndex += varlength - shiftBits;  
101.                 shiftBits = 2 * shiftBits - varlength;  
102.             }  
103.             varlength = endIndex - beginIndex + 1;  
104.         }  
105.         return arr;  
106.     }  
107.       
108.     /* 
109.      * exchange: 将指定的数组区域内容互换，具体来说， 
110.      * arr[beginIndex1:beginIndex1+length-1] 与 arr[beginIndex2, beginIndex2+length-1] 的内容依次互换，即 
111.      * arr[beginIndex1] 与 arr[beginIndex2] 互换， ... arr[beginIndex1+length-1] 与 arr[beginIndex2+length-1] 互换. 
112.      * 前置条件： 指定数组区域不能超过数组范围，且区域互不重叠  
113.      *  
114.      */  
115.     private static void exchange(int[] arr, int beginIndex1, int beginIndex2, int length)  
116.     {  
117.         checkParametersForExchange(arr, beginIndex1, beginIndex2, length);  
118.         for (int k=0; k < length; k++) {  
119.             int temp = arr[k+beginIndex1];  
120.             arr[k+beginIndex1] = arr[k+beginIndex2];  
121.             arr[k+beginIndex2] = temp;  
122.         }  
123.     }  
124.       
125.     private static void checkParametersForExchange(int[] arr, int beginIndex1, int beginIndex2, int length)  
126.     {  
127.         if (beginIndex1 + length-1 >= arr.length || beginIndex2 + length-1 >= arr.length) {  
128.             throw new IllegalArgumentException("参数错误，指定数组区域超过数组范围!");  
129.         }  
130.         if (Math.abs(beginIndex1 - beginIndex2) + 1 <= length)   
131.             throw new IllegalArgumentException("参数错误，指定数组区域不能重叠!");  
132.     }  
133.       
134.     /** 
135.      * leftShift: 基于数组逆置法求解向量旋转问题 
136.      */  
137.     public static int[] leftShift(int[] arr, int i)  
138.     {  
139.         int shiftBits = processParameters(arr, i);  
140.         if (shiftBits == 0) {  
141.             return arr;  
142.         }  
143.         reverse(arr, 0, shiftBits-1);  
144.         reverse(arr, shiftBits, arr.length-1);  
145.         reverse(arr, 0, arr.length-1);  
146.         return arr;  
147.     }  
148.       
149.     /** 
150.      * reverse: 将数组的指定区域逆置 
151.      * @param beginIndex 指定区域的起始下标 
152.      * @param endIndex 指定区域的终止下标(包含) 
153.      */  
154.     public static void reverse(int[] arr, int beginIndex, int endIndex)  
155.     {  
156.         checkParameterForReverse(arr, beginIndex, endIndex);  
157.         int length = endIndex - beginIndex + 1;  
158.         for (int k=beginIndex; k < beginIndex + (length+1)/2; k++) {  
159.             int temp = arr[k];  
160.             arr[k] = arr[beginIndex + endIndex -k];  
161.             arr[beginIndex + endIndex -k] = temp;  
162.         }  
163.     }  
164.       
165.     private static void checkParameterForReverse(int[] arr, int beginIndex, int endIndex)  
166.     {  
167.         if (beginIndex < 0 || endIndex < 0 || beginIndex >= arr.length || endIndex >= arr.length) {  
168.             throw new IllegalArgumentException("指定区域 [" + beginIndex + "," + endIndex + "] 错误, 参数必须均为正整数，且不能超过数组长度 " + arr.length);   
169.         }  
170.         if (beginIndex > endIndex) {  
171.             throw new IllegalArgumentException("指定区域 [" + beginIndex + "," + endIndex + "] 错误，第一个参数必须不大于第二个参数!");  
172.         }  
173.     }  
174.       
175.     /* 
176.      * processParameters: 进行参数处理，若不合法，抛出异常；若合法，返回实际需要移位的位数 
177.      */  
178.     private static int processParameters(int[] arr, int i)  
179.     {  
180.         if (i < 0) {  
181.             throw new IllegalArgumentException("参数错误，指定移位位数必须是正整数！");  
182.         }  
183.         int shiftBits = i % arr.length;  
184.         return shiftBits;  
185.     }  
186.       
187.     static class Tester {  
188.           
189.         public static void testLeftShift(int[] arr, int i) {  
190.             System.out.println("将向量 " + Arrays.toString(arr) + " 循环左移 " + i + " 位：/t");  
191.             try {  
192.                 int[] copy = Arrays.copyOf(arr, arr.length);  
193.                 System.out.println(Arrays.toString(leftShift(copy, i)) + " /t*** leftShift ");  
194.                 copy = Arrays.copyOf(arr, arr.length);  
195.                 System.out.println(Arrays.toString(leftShift2(copy, i)) + " /t*** leftShift2 ");  
196.                 copy = Arrays.copyOf(arr, arr.length);  
197.                 System.out.println(Arrays.toString(leftShift3(copy, i)) + " /t*** leftShift3 ");  
198.                 copy = Arrays.copyOf(arr, arr.length);  
199.                 System.out.println(Arrays.toString(leftShift4(copy, i)) + " /t*** leftShift4 ");  
200.                   
201.             } catch (Exception e) {  
202.                 System.out.println(e.getMessage());  
203.             }  
204.         }  
205.           
206.         public static void testExchange() {  
207.             int[] arr = new int[] {1,2,3,4,5,6,7,8,9};  
208.             for (int i = 1; i <= 6; i++) {  
209.                 int[] copy = Arrays.copyOf(arr, arr.length);  
210.                 try {  
211.                    exchange(copy, 2, 5, i);  
212.                    System.out.println("i = " + i + "/t" + Arrays.toString(copy));  
213.                 } catch (Exception e) {  
214.                     System.out.println(e.getMessage());  
215.                 }  
216.             }  
217.         }  
218.           
219.         public static void testReverse() {  
220.             int[] arr = new int[] {1,2,3,4,5,6,7,8,9};  
221.             for (int i = 0; i < arr.length; i++) {  
222.                 int[] copy = Arrays.copyOf(arr, arr.length);  
223.                 try {  
224.                    reverse(copy, i, arr.length-i);  
225.                    System.out.println("i = " + i + "/t" + Arrays.toString(copy));  
226.                 } catch (Exception e) {  
227.                     System.out.println(e.getMessage());  
228.                 }  
229.             }  
230.         }  
231.           
232.         public static void testGCD()  
233.         {  
234.             int n = 200, m = 100;   
235.             while(n>=-10 && m >=-10) {  
236.                     try {  
237.                         System.out.println("[" + n + "," + m + "] 的最大公约数是 ：" + gcd(m, n));  
238.                     } catch (Exception e) {  
239.                         System.out.println(e.getMessage());  
240.                     }  
241.                     n-= 5; m-=3;  
242.                 }  
243.         }  
244.           
245.         public static void main(String[] args)  
246.         {  
247.             System.out.println("************* 最大公约数 **************");  
248.             testGCD();  
249.               
250.             System.out.println("************* 数组区域内容交换 ****************");    
251.             testExchange();  
252.               
253.             System.out.println("************* 数组逆置 ****************");    
254.             testReverse();  
255.                       
256.             System.out.println("************* 向量旋转 ****************");  
257.               
258.             testLeftShift(new int[] {1,2,3,4,5,6,7,8,9,10}, 3);  
259.             testLeftShift(new int[] {1,2,3,4,5,6,7,8,9,10}, 4);  
260.             testLeftShift(new int[] {1,2,3,4,5,6,7,8,9,10}, 8);  
261.             testLeftShift(new int[] {1,2,3,4,5,6,7,8,9,10}, 13);  
262.             testLeftShift(new int[] {1,2,3,4,5,6,7,8,9,10}, 30);  
263.             testLeftShift(new int[] {1,2,3,4,5,6,7,8,9,10}, 0);  
264.             testLeftShift(new int[] {1,2,3,4,5,6,7,8,9,10}, -1);      
265.               
266.         }  
267.     }  
268. }