基于字典序输出全排列-训练常用实用类相关知识

     本文的目的是训练初学Java者使用String以及StringBuffer类。便于掌握类的相关方法,作为课外读物配合主教材的学习。

  (1) 字典序

     每个字符（char型数据）都在Unicode表中有自己的顺序位置，比如字符a的位置就是97，即表达式(int)'a'的值是97。字符1至9的位置分别是49至57，即表达式'1'<'2'的值是true。 对于String对象的字符序列，可以按“字典序”比较大小。比较大写的规则是，如果二者含有的字符完全相同，就称二者相等，否则，从左(0索引位置开始)向右比较字符序列中的字符，当在某个位置出现不相同的字符时，停止比较，二者根据根据该位置上字符的大小关系确定“字典序”的大小关系。比如"125364"和"126453"，按字典序,"125364"就小于"126453"即"125364"compareTo("126453")的值小于0。"6521"compareTo("65")的值就大于0。

（2）全排列（不重复的）

     例如字符1,2,3因组成的（不重复）的全排列共有3!个，即6个  ：   

     123, 132,213, 231 ,312 321

（3）全排列按字典序排序

      例如，对于字符1,2,3,5,6,7,8组成的全排列。按字典序，最小的是：

      "12345678"

      最大的是

      "87654321"。

      从最小的全排列（或最大的全排列）开始，按着字典序依次寻找下一个全排列，一直到找到最大的（最小的）全排列为止，就可以按着字典序给出全部的全排列。

     那么怎么按字典序，从一个全排列找一下个全排列呢？

     假如要找 "34587621"的下一个全排列。

     在全排列的相邻对中找到相邻对是大小“正序”（小的在前，大的在后）的最后一对：

      例如 ‘5’<‘8’是‘3’<‘4’，‘4’<‘5’，‘5’<‘8’的最后一对。

      记住这个最后相邻对的起始位置，例如位置2相邻对58的起始位置（String字符序列的起始位置是0），用k存储这个位置：

          k = 2

  如图：

（如果找不到“正序”相邻对，那么这个全排列一定是最大的那个，例如：      "87654321"中就没有“正序”的相邻对）。

       那么显然可知，这个全排列从位置k+1开始的字符是按从大到小排列的（相邻对是反序的，即大的在前，小的在后）。如图所示意。

           然后，在全排列的字符中，从k+1开始，找比相邻对的首字符大的而且是最小字符（一定能找到，因为k+1位置的字符就比邻对的首字符大）。

       例如找到的字符是6（字符6以后的字符（假如有的话）都比字符4小），如图所示。

       然后将找到的字符与相邻对的首字符互换，反转后的效果如图所示：

      再将全排列从k+1位置开始的字符序列反转（该字符序列中也可能就一个字符），如图：

那么此时得到的全排列：

       34612578   是 34587621（当前排列）的下一个排列

       因为，按着前面的找相邻对的规则可知，找到的34612578和原来的34587621二者刚好在位置2的位置出现了不相同的字符（而且'6'>'5'），那么按着字典序“34612578”是刚好大于“34587621”，理由是，该全排列的剩余字符，即从位置k+1开始的字符：8，7，6，2和1，是从小到大排列的（再没有反序的相邻对，保证了最小性）。

  （4）代码

   按字典序输出全排列属于经典算法之一，大部分都是用数组实现的，这里我们用java的String和StringBuffer类的对象来完成，便于掌握类的相关方法,作为课外读物配合教材的学习。   借助String和StringBuffer类输出全排列的代码和运行效果如下：

Arrangement.java

public interface Arrangement {

    public void inputFullArrangement(String s); //输出全排列

}

App.java

public class App{

    public static void main(String args[]){

        Arrangement stu = new Student();

        System.out.println("输出12345的全排列");

        stu.inputFullArrangement("12345"); //输出全排列

    }

}

Student.java

public class Student implements Arrangement{

    public void inputFullArrangement(String s){ //输出全排列

        StringBuffer nextString = new StringBuffer(s);

        StringBuffer temp = new StringBuffer(s);

        String MAX = new String(temp.reverse());

        int count =0;

        while(!nextString.toString().equals(MAX)){

           nextString = findNextString(nextString);

           System.out.print(nextString+","); 

           count++;

           if(count%12==0)

             System.out.println();

        } 

    }

    public StringBuffer findNextString(StringBuffer s){

        int k = -1;

        StringBuffer nextString = new StringBuffer();

        for(int i=0;i<s.length()-1;i++) { 

            if(s.charAt(i)<s.charAt(i+1)){

                k = i;

            }

        }

        char ch = s.charAt(k);

        char max =  s.charAt(k+1);//k+1位置的字符比ch大

        int position = -1; 

        for(int i=k+1;i<=s.length()-1;i++) {

            if(s.charAt(i)>ch&&s.charAt(i)<=max){

                position = i;

                max = s.charAt(i);

            }

        } 

        char findChar = s.charAt(position);

        s.setCharAt(position,ch);

        s.setCharAt(k,findChar); 

        StringBuffer suffix = new StringBuffer(s.substring(k+1));

        suffix = suffix.reverse();//把从k+1位置开始的字符序列反转

        nextString = nextString.append(s.substring(0,k+1));

        nextString = nextString.append(suffix);

        return nextString;

    }

}