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

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

(1) 字典序

  每个字符（char型数据）都在Unicode表中有自己的顺序位置，比如字符a的位置就是97，即表达式(int)'a'的值是97。字符1至9的位置分别是49至57，即表达式'1'当在某个位置出现不相同的字符时，停止比较，二者根据根据该位置上字符的大小关系确定“字典序”的大小关系。比如"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组成的全排列。按字典序，最小的是：

    最大的是

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

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

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

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

    例如‘5’是‘3’

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

k = 2

如图：

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

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

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

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

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

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

那么此时得到的全排列：

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

（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();

      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);

         count++;

         if(count%12==0)

      }

  }

  public StringBuffer findNextString(StringBuffer s){

      int k = -1;

      StringBuffer nextString = new StringBuffer();

      for(int i=0;i

          if(s.charAt(i)

              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

          if(s.charAt(i)>ch&&s.charAt(i)

              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;

  }

}