编程珠玑-翻转算法

问题：将一个n元一维向量向左旋转i个位置。如，当n=8且i=3时，向量abcdefgh旋转为defghabc.求解决方案。

1.         首先将x的前i个元素复制到一个临时数组中，然后将余下的n-i个元素向左移动i个位置，最后将最初的i个元素从临时数组中复制到x中余下的位置。但是，这种办法使用的i个额外位置产生了过大的存储空间消耗。

2.         定义一个函数将x向左旋转一个位置然后调用该函数i次。但该方法又产生了过多的运行时间消耗。

3.         要在有限的资源内解决该问题，显然需要更复杂的程序。有一个成功的方法有点像精巧的杂技动作：移动x[0]到临时变量t,然后移动x[i]至x[0],x[2i]至x[i],依次类推（将x中的所有下标对n取模），直至返回到取x[0]中的元素，此时改为从t取值然后终止过程。

4.         我们将问题看成把数组ab转换成ba，同时假定我们拥有一个函数可以将数组中的特定部分元素求逆。从ab开始，先对a求逆，得到a^r b,然后对b求逆，得到a^r b^r  ，然后整体求逆，得到（a^r b ^r）^r 。此时就是ba。

 

 

杂技算法的代码：

package bczj.chapter2;

 

import java.util.ArrayList;

import java.util.Collections;

import java.util.List;

 

import com.util.MyList;

 

/**

 *

 *

 * Title:杂技算法 <br>

 * Description: <br>

 * Copyright: Copyright (c) 2007<br>

 * Company:xx有限公司<br>*

 * @author yingkh

 * @version 1.0

 * @date 2010-8-3

 */

public class Acrobatics {

        

         public Acrobatics(){

                  

         }

 

         public List<String> rotation(List<String> list, int rotdist) {

                   //最大公约数(Greatest common divisor)

                   int m = gcd (rotdist,list.size());

                  int j = 0;

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

                            String temp = list.get(i);

                            j = i;

                            while(true) {

                           

                            int k = j + rotdist;

                            if(k >= list.size()) {

                                     k -= list.size();

                            }

                            if( k== i) {

                                     break;

                            }

                            list.set(j, list.get(k));

                            j = k;

                            }

                            list.set(j, temp);

                   }

                   return list;

         }

        

         //求最大公约数

         private int gcd(int i, int j) {

                   while(i != j) {

                            if(i > j){

                                     i -= j;

                            }else {

                                     j -= i;

                            }                          

                   }

                   return i;

         }

        

        

         /**

          * @param args

          */

         public static void main(String[] args) {

                   Acrobatics ac = new Acrobatics();

                   MyList myList = new MyList();

                   List list = myList.createStringList(6);

                   List result = ac.rotation(list, 3);

                   myList.print(result);

                  

         }

 

}

 

/*

 * 编程珠玑：将一个n元一维向量向左旋转i个位置。如当n=8,i=3时，向量abcdefgh旋转为

 * defghabc.

 *

 * */

 

旋转算法：

package bczj.chapter2;

 

import java.util.Collections;

import java.util.List;

 

import com.util.MyList;

 

/**

 *

 *

 * Title:翻转数组 <br>

 * Description: <br>

 * Copyright: Copyright (c) 2007<br>

 * Company:XX限公司<br> *

 * @author yingkh

 * @version 1.0

 * @date 2010-8-3

 */

public class InverseArray {

        

         public InverseArray() {

                  

         }

        

         //翻转元素

         private List<String> reverseList(List<String> list, int begin, int end) {

                   if(begin <= end) {

                            for(int i = begin; i < end; i++,end--) {

                                     if(i<end-1) {

                                     String temp = list.get(i);

                                     list.set(i, list.get(end-1));

                                     list.set(end-1, temp);

                                     }

                            }

                   }

                   return list;

         }

 

         /**

          * @param args

          */

         public static void main(String[] args) {

                   Acrobatics ac = new Acrobatics();

                  

                   MyList myList = new MyList();

                   List list = myList.createStringList(10);

                  

                   InverseArray inverseArray = new InverseArray();

                   inverseArray.reverseList(list, 0, 5);

                   inverseArray.reverseList(list, 5, 10);

                   inverseArray.reverseList(list, 0, 10);

        

                   myList.print(list);*/

         }

 

}

 

公用的myList类：

package com.util;

 

import java.util.ArrayList;

import java.util.List;

 

public class MyList {

        

         public MyList() {

                  

         }

        

         //产生String类型的list

         public List<String> createStringList(int length) {

                   List<String> list = new ArrayList<String>();

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

                            list.add(String.valueOf(i));

                   }

                   return list;

         }

        

         //打印list

         public void print(List<String> list) {

                   for(int i=0; i<list.size() ;i++) {

                            System.out.println("第"+i+"个元素为： "+list.get(i));

                   }

         }

        

}

 

 

其实Collection中已经有这个算法了，Collections.rotate()方法。

rotate

public static void rotate(List<?> list,int distance)根据指定的距离轮换指定列表中的元素。调用此方法后，对于 0 和 list.size()-1（包括）之间的所有 i 值，索引 i 处的元素将是以前位于索引 (i - distance) mod list.size() 处的元素。（此方法对列表的大小没有任何影响。） 例如，假设 list 包含 [t, a, n, k, s]。在调用 Collections.rotate(list, 1)（或 llections.rotate(list, -4)）之后，list 将包含 [s, t, a, n, k]。 注意，此方法用于子列表时非常有用，可以在保留其余元素顺序的同时，在列表中移动一个或多个元素。例如，以下语句可以将索引 j 处的元素向前移动到位置 k 上（k 必须大于等于 j）：      Collections.rotate(list.subList(j, k+1), -1);为了具体说明这一点，假设 list 包含 [a, b, c, d, e]。要将索引 1 处的元素（b）向前移动两个位置，请执行以下调用：      Collections.rotate(l.subList(1, 4), -1); 得到的列表是 [a, c, d, b, e]。

 

我们来看一下它的源码吧：

 

    private static final int ROTATE_THRESHOLD         =  100;

public static void rotate(List<?> list, int distance) {

        if (list instanceof RandomAccess || list.size() < ROTATE_THRESHOLD)

            rotate1((List)list, distance);

        else

            rotate2((List)list, distance);

    }

 

    private static <T> void rotate1(List<T> list, int distance) {

        int size = list.size();

        if (size == 0)

            return;

        distance = distance % size;

        if (distance < 0)

            distance += size;

        if (distance == 0)

            return;

 

        for (int cycleStart = 0, nMoved = 0; nMoved != size; cycleStart++) {

            T displaced = list.get(cycleStart);

            int i = cycleStart;

            do {

                i += distance;

                if (i >= size)

                    i -= size;

                displaced = list.set(i, displaced);

                nMoved ++;

            } while(i != cycleStart);

        }

    }

 

    private static void rotate2(List<?> list, int distance) {

        int size = list.size();

        if (size == 0)

            return;

        int mid =  -distance % size;

        if (mid < 0)

            mid += size;

        if (mid == 0)

            return;

 

        reverse(list.subList(0, mid));

        reverse(list.subList(mid, size));

        reverse(list);

    }

 

很有趣，当list的长度小于100时，list默认用的是杂技算法，否则用的是翻转算法。

另外我们看一下list的reverse方法，写的很精妙：

   public static void reverse(List<?> list) {

        int size = list.size();

        if (size < REVERSE_THRESHOLD || list instanceof RandomAccess) {

            for (int i=0, mid=size>>1, j=size-1; i<mid; i++, j--)

                swap(list, i, j);

        } else {

            ListIterator fwd = list.listIterator();

            ListIterator rev = list.listIterator(size);

            for (int i=0, mid=list.size()>>1; i<mid; i++) {

       Object tmp = fwd.next();

                fwd.set(rev.previous());

                rev.set(tmp);

            }

        }

    }

同样，swap方法：

  public static void swap(List<?> list, int i, int j) {

    final List l = list;

    l.set(i, l.set(j, l.get(i)));

    }

 

 

ArrayList的set方法：

 

  public E set(int index, E element) {

    RangeCheck(index);

    E oldValue = (E) elementData[index];

    elementData[index] = element;

    return oldValue;

    }

不得不感叹java的源码，确实精妙。