数组的循环右移

一、第一反应

对于初次遇到此命题的人，一般都会这么做：

先设置一个临时变量，将数组最后一个存入变量，然后将数组中前n-1个，从最后一个开始，依次存入后面一个位置，

这样做的效果就把前n-1个整体向右平移一个单位，再把临时变量的值存入数组头，如此数组完成了向右循环移动1位的工作，

再外加一个循环控制，循环右移k次，于是便完成了。代码如下：

template<typename T>

void cycle_move(T* array,int n,int k) {     

     for(int i = 0;i < k;i++)             //k次循环右移

     {

         T temp = array[n-1];             //设置零时变量

         for(int j = n - 1;j > 0 ;j--)

              array[j] = array[j - 1];

         array[0] = temp;

     }

}

这是最直观的解法，算法外循环k次，内循环n-1次，k (k=1,2…n-1)是个随机值,等概率分布，

循环次数的数学期望=[1*1/(n-1)+2*/(n-1)+…+(n-1)*1/(n-1)]*(n-1)=n(n-1)/2,

所以时间复杂度为O(n2)，空间复杂度为O(1)。时间复杂度难以让人接受。

二、换位思考

前一种方法目的是将后面的k个数据一个个的移到前面，可以换过来想想:将前面的一次性放到所要放的地方。

如：0 1 2 3 4 5 6 7右移3位

将0移到第三位，1移到第1+3位……如此原来的数需要保存，

于是可以很容易想到：将0和3交换，但3也需要移到3+3位，于是可以交换此时的第0位和第6位，于是交换后第0位是6，

而此时的6+3位则需要取8的模（6+3）%8=1，于是跟第1位交换……

于是大概的雏形便出现了：每次用第一位跟第（i+k）% n位的数据交换，终止条件是模为0。

伪代码如下：

貌似很简单，但是问题便出来了，（i+k）% n能访问到数组中所有的位置吗？

如果能，那么每个位置是否只被访问了一次？下面将继续探讨。

三、深入探讨

首先举几个例子。

例一：0 1 2 3 4 5 6 7右移3位（n=8,k=3）

第1次 3 1 2 0 4 5 6 7

第2次 6 1 2 0 4 5 3 7

第3次 1 6 2 0 4 5 3 7

第4次 4 6 2 0 1 5 3 7

第5次 7 6 2 0 1 5 3 4

第6次 2 6 7 0 1 5 3 4

第7次 5 6 7 0 1 2 3 4

循环了7次，i访问了所有点，且仅仅访问了一次。

例二：0 1 2 3 4 5 6 7 8右移3位（n=9,k=3）

第1次 3 1 2 0 4 5 6 7 8

第2次 6 1 2 0 4 5 3 7 8

第3次时i = (i+k)%n = 0;

于是出故障了。

例三：0 1 2 3 4 5 6 7 8右移6位（n=9,k=6）

第1次 6 1 2 3 4 5 0 7 8

第2次 3 1 2 6 4 5 3 7 8

第3次时i = (i+k)%n = 0;

于是也出故障了。

再细想一下也很容易发现，

当n是k的整数倍时，循环（n/k – 1）次一定会回到第0位，这是很显然的。

而且条件可以更宽些，当n跟k不是互质时，循环[ n/(n,k) – 1 ]次也会回到第0位( (n,k)表示n和k的最大公约数)。

于是我们先看看(n,k) = 1时(即互质)。

1. (n,k) = 1时的情况

这个证明很简单：

<1>我们可以先取j = 0; j = j + k;

 跟i同时循环，则I = (I + k)%n 跟 j%n 是等价的。

 当I = (I + k)%n = 0时，则有j%n = 0，

而j = j + k = pk (j初值为0，p为一正整数)，于是pk%n = 0，即 pk是n的倍数，而k跟n是互质的，

所以p是n的倍数，又因为只要pk%n = 0,则退出，

所以p是n最小的倍数，所以必有p = n。

所以i共访问了n个元素。

<2>因为I = j%n，

设不同时刻的i1,i2，i1 – i2 = (j1 – j2)%n = (p1*k – p2*k)%n = (p1 – p2)*k%n，

若i1 = i2，则p1 – p2一定是n的倍数，

显然不同时刻p1 != p2(因为j是递增的)，

所以任意时刻i1 != i2。即i对n产生的模互不相等。

<3>综合1、2，得i对n的所有余数一一映射，则必然可以得到i可以访问数组中的每一个元素，且仅访问一次。

于是对于(k,n) = 1的情况可以写出代码：

template<typename T>

void cycle_move(T* array,int n,int k) { 

     int i = 0;

     while((i = (i + k) % n) != 0)

         swap(array[0],array[i]);

}

2.考虑(k,n) != 1的情况

这种情况，有一个及其简单的思路----分段。

设(k,n) = m，则可以把n个数看成每段长度为m的n/m段数据的集合。例如:

0 1 2 3 4 5 6 7 8右移6位（n=9, k=6, m=3）

可以看成：

{0 1 2} {3 4 5} {6 7 8}  3段，

此时向右移动6位即将这三段向右移动2 段(2 = k / m)，鉴于前面的程序，

则可以将每段中同一个位置的元素看成可以移动的集合，

如{0 3 6}，此时的n’跟k’必然是互质的，于是可以内嵌上面的一段程序。

于是可以这样组织代码：

int greatest_common(int m,int n)      //求出最大公约数

{

     int r;

     while(r = m % n)   {    m = n;   n = r;   }

     return n;

}

template<typename T>

void cycle_move(T* array, int n, int k) {

     int r = greatest_common(n,k);

     for(int i=0; i<r; i++) {

         int j = i;

         while((j = (j + k) % n) != i)

              swap(array[0],array[j]);

     }

}

四、多一点思考

前面所做的一切都是为了这段代码，而这段代码却如此简练。

复杂度分析：

求最大公约数时间复杂度为O(logn), cycle_move循环次数为n，而logn < n

所以该算法时间复杂度为O(n)。空间复杂度为O(1)，产生在交换中。

事情到这里似乎已经很完美了，但何不多想一点？

这个程序最不好的地方在哪里呢？

很显然，最不好的地方在交换！每循环一次就得交换一次，二交换的实现类似于：

template<typename T>

void swap(T& left,T& right) {

     T temp = left;

     left = right;

     right = temp;

}

需要频繁地使用数组下表和这三个赋值语句，这就是我们需要改善的。

那么如何避免交换呢？

下面仍然先从(k,n) = 1说起。

前一种方法中，所有数据通过第0位作中转，以存储到目标位置，这就是交换产生的原因。

如果另设一个中转的变量temp，源数据保存在temp中，每次需要将temp中的数据存到目标位，

但此时目标位的数据就需要保存下来，如果保存下来了，则以此类推，得到最后一个被访问的（也就是第0位）需要被保存。

这样一来就豁然开朗了：只要先保存第0位，然后按照跟前面 i 访问次序相反的次序访问，就可以不被覆盖。于是又得到下面的代码：

template<typename T>

void cycle_move(T* array,int n,int k) {

     T temp = array[0];

     int i = 0, prei;

     while((prei = (n + i - k) % n) != 0) {

         array[i] = array[prei];

         i = prei;

     }

     array[i] = temp;

}

于是对于(k,n)!=1的情况可以这样组织代码：

template<typename T>

void cycle_move(T* array,int n,int k) {

     int r = greatest_common(k,n);

     int temp;

     int prej,j;

     for(int i=0; i<r;i++) {

         temp = array[i];

         j = i;

         while((prej = (n + j - k) % n) != i) {

              array[j] = array[prej];

              j = prej;

         }

         array[j] = temp;

     }

}

这样做时间复杂度和空间复杂度都没有改变，但效率增加了一个常量倍数，也是很值得的。

到此为止我所了解的循环移位算法已经是达到最佳了。

五、技巧篇

上面的算法的确比较高效，但理解起来似乎比较困难。

偶然间发现了一个理解起来很容易，效率也比较令人满意的算法----转置法。

可以用线性代数中一个简单的公式解释：

序列A = ab，循环后得到B = ba，

伪代码如下：

代码尤其简单：

template<typename T>

void cycle_move(T* array,int n,int k) {

     int kt = n - k;

     reverse(array, array+kt);

     reverse(array+kt, array+n);

     reverse(array, array+n);

}

时间复杂度为O(n)，空间复杂度为O(1)，但从效率上讲不如上面的一个程序。

六、一点启发

上面前五点是我自己推敲的结果，回过头来看看我的推导过程，感觉这里存在着一种很好的思维方式。

从一般解逐步追求卓越的解，这种由浅入深的及其有条理的思维起到了关键作用。

这是我自己独立思考并成功获得第一个精简算法，我会好好从这段过程中吸取经验，以获得更多的成果。

希望大家支持我的想法。