一、递归算法

/
1、递归算法

解析：http://www.cnblogs.com/cxjchen/p/3932949.html (感谢该文作者！)

* 对于无重复值的情况

 固定第一个字符，递归取得首位后面的各种字符串组合；
再把第一个字符与后面每一个字符交换，并同样递归获得首位后面的字符串组合； 递归的出口，就是只剩一个字符的时候，递归的循环过程，就是从每个子串的第二个字符开始依次与第一个字符交换，然后继续处理子串。

 假如有重复值*呢？
由于全排列就是从第一个数字起，每个数分别与它后面的数字交换，我们先尝试加个这样的判断——如果一个数与后面的数字相同那么这两个数就不交换了。
 例如abb，第一个数与后面两个数交换得bab，bba。然后abb中第二个数和第三个数相同，就不用交换了。
但是对bab，第二个数和第三个数不 同，则需要交换，得到bba。
 由于这里的bba和开始第一个数与第三个数交换的结果相同了，因此这个方法不行。

 换种思维，对abb，第一个数a与第二个数b交换得到bab，然后考虑第一个数与第三个数交换，此时由于第三个数等于第二个数，
所以第一个数就不再用与第三个数交换了。再考虑bab，它的第二个数与第三个数交换可以解决bba。此时全排列生成完毕！
 @param str
@return
/

代码

  1. public class Solution {
  2.     public static void main(String[] args)
  3.     {
  4.         ArrayList<String> list = Permutation("abcd");
  5.         for(int i = 0;i<list.size();i++)
  6.         {
  7.             System.out.println(list.get(i));
  8.         }
  9.     }
  10.     public static ArrayList<String> Permutation(String str){
  11.         ArrayList<String> list = new ArrayList<String>();
  12.         if(str!=null && str.length()>0){
  13.             PermutationHelper(str.toCharArray(),0,list);
  14.             Collections.sort(list);
  15.         }
  16.         return list;
  17.         }
  18.      public static void PermutationHelper(char[] ch,int p,ArrayList<String> list) {
  19.          if(p==ch.length-1)
  20.          {
  21.              list.add(String.valueOf(ch));
  22.          }else
  23.          {
  24.              Set<Character> charSet = new HashSet<Character>(); 
  25.              for(int i=p;i<ch.length;i++)
  26.              {
  27.                  //判断是否有重复的字符
  28.                  if(!charSet.contains(ch[i]))
  29.                  {
  30.                      charSet.add(ch[i]);
  31.                      swap(ch,i,p);//把递归放到黑盒子里,不用思考它怎么运行的,理解调用递归的思路就可以
  32.                      PermutationHelper(ch, p+1, list);
  33.                      swap(ch,i,p);
  34.                  }
  35.              }
  36.          }           
  37.      }
  38.      public static void swap(char[] ch,int i,int j)
  39.      {
  40.          char temp;
  41.          temp = ch[i];
  42.          ch[i] = ch[j];
  43.          ch[j] = temp;         
  44.      }
  45. }

二、字典序

代码

  1. public ArrayList<String> Permutation(String str) {
  2.        ArrayList<String> res = new ArrayList<>();
  4.         if (str != null && str.length() > 0) {
  5.             char[] seq = str.toCharArray();
  6.             Arrays.sort(seq); //排列
  7.             res.add(String.valueOf(seq)); //先输出一个解
  9.             int len = seq.length;
  10.             while (true) {
  11.                 int p = len - 1, q;
  12.                 //从后向前找一个seq[p - 1] < seq[p]
  13.                 while (p >= 1 && seq[p - 1] >= seq[p]) --p;
  14.                 if (p == 0) break; //已经是“最小”的排列，退出
  15.                 //从p向后找最后一个比seq[p]大的数
  16.                 q = p; --p;
  17.                 while (q < len && seq[q] > seq[p]) q++;
  18.                 --q;
  19.                 //交换这两个位置上的值
  20.                 swap(seq, q, p);
  21.                 //将p之后的序列倒序排列
  22.                 reverse(seq, p + 1);
  23.                 res.add(String.valueOf(seq));
  24.             }
  25.         }
  27.         return res;
  28.     }
  30.     public static void reverse(char[] seq, int start) {
  31.         int len;
  32.         if(seq == null || (len = seq.length) <= start)
  33.             return;
  34.         for (int i = 0; i < ((len - start) >> 1); i++) {
  35.             int p = start + i, q = len - 1 - i;
  36.             if (p != q)
  37.                 swap(seq, p, q);
  38.         }
  39.     }
  41.     public static void swap(char[] cs, int i, int j) {
  42.         char temp = cs[i];
  43.         cs[i] = cs[j];
  44.         cs[j] = temp;
  45.     }

三、递归法二

代码

  1. import java.util.ArrayList;
  2. import java.util.List;
  3. import java.util.Collections;
  4. public class Solution {
  5.     public ArrayList<String> Permutation(String str) {
  6.         List<String> resultList = new ArrayList<>();
  7.         if(str.length() == 0)
  8.             return (ArrayList)resultList;
  9.         //递归的初始值为（str数组，空的list，初始下标0）
  10.         fun(str.toCharArray(),resultList,0);
  11.         Collections.sort(resultList);
  12.         return (ArrayList)resultList;
  13.     }
  15.     private void fun(char[] ch,List<String> list,int i){
  16.         //这是递归的终止条件，就是i下标已经移到char数组的末尾的时候，考虑添加这一组字符串进入结果集中
  17.         if(i == ch.length-1){
  18.             //判断一下是否重复
  19.             if(!list.contains(new String(ch))){
  20.                 list.add(new String(ch));
  21.                 return;
  22.             }
  23.         }else{
  24.             //这一段就是回溯法，这里以"abc"为例
  26.             //递归的思想与栈的入栈和出栈是一样的,某一个状态遇到return结束了之后，会回到被调用的地方继续执行
  28.             //1.第一次进到这里是ch=['a','b','c'],list=[],i=0，我称为 状态A ，即初始状态
  29.             //那么j=0，swap(ch,0,0)，就是['a','b','c']，进入递归，自己调自己，只是i为1，交换(0,0)位置之后的状态我称为 状态B 
  30.             //i不等于2，来到这里，j=1，执行第一个swap(ch,1,1)，这个状态我称为 状态C1 ,再进入fun函数，此时标记为T1，i为2，那么这时就进入上一个if，将"abc"放进list中
  31.             /////////////-------》此时结果集为["abc"]
  33.             //2.执行完list.add之后，遇到return，回退到T1处，接下来执行第二个swap(ch,1,1)，状态C1又恢复为状态B
  34.             //恢复完之后，继续执行for循环，此时j=2,那么swap(ch,1,2),得到"acb"，这个状态我称为C2,然后执行fun，此时标记为T2,发现i+1=2,所以也被添加进结果集，此时return回退到T2处往下执行
  35.             /////////////-------》此时结果集为["abc","acb"]
  36.             //然后执行第二个swap(ch,1,2)，状态C2回归状态B,然后状态B的for循环退出回到状态A
  38.             //             a|b|c(状态A)
  39.             //               |
  40.             //               |swap(0,0)
  41.             //               |
  42.             //             a|b|c(状态B)
  43.             //             /  \
  44.             //   swap(1,1)/    \swap(1,2)  (状态C1和状态C2)
  45.             //           /      \
  46.             //         a|b|c   a|c|b
  48.             //3.回到状态A之后，继续for循环，j=1,即swap(ch,0,1)，即"bac",这个状态可以再次叫做状态A,下面的步骤同上
  49.             /////////////-------》此时结果集为["abc","acb","bac","bca"]
  51.             //             a|b|c(状态A)
  52.             //               |
  53.             //               |swap(0,1)
  54.             //               |
  55.             //             b|a|c(状态B)
  56.             //             /  \
  57.             //   swap(1,1)/    \swap(1,2)  (状态C1和状态C2)
  58.             //           /      \
  59.             //         b|a|c   b|c|a
  61.             //4.再继续for循环，j=2,即swap(ch,0,2)，即"cab",这个状态可以再次叫做状态A，下面的步骤同上
  62.             /////////////-------》此时结果集为["abc","acb","bac","bca","cab","cba"]
  64.             //             a|b|c(状态A)
  65.             //               |
  66.             //               |swap(0,2)
  67.             //               |
  68.             //             c|b|a(状态B)
  69.             //             /  \
  70.             //   swap(1,1)/    \swap(1,2)  (状态C1和状态C2)
  71.             //           /      \
  72.             //         c|b|a   c|a|b
  74.             //5.最后退出for循环，结束。
  76.             for(int j=i;j<ch.length;j++){
  77.                 swap(ch,i,j);
  78.                 fun(ch,list,i+1);
  79.                 swap(ch,i,j);
  80.             }
  81.         }
  82.     }
  84.     //交换数组的两个下标的元素
  85.     private void swap(char[] str, int i, int j) {
  86.             if (i != j) {
  87.                 char t = str[i];
  88.                 str[i] = str[j];
  89.                 str[j] = t;
  90.             }
  91.         }
  92.     }

四、回溯法

代码

  1. public class Solution {
  2.     private static ArrayList<String> res = new ArrayList<>();
  3.     private static TreeSet<String> paths = new TreeSet<>();
  4.     private static StringBuilder path = new StringBuilder();
  5.     private static boolean[] visited;
  7.     public static void main(String[] ags)
  8.     {
  9.         ArrayList<String> list = Permutation("abc");
  10.         for(int i = 0;i<list.size();i++) {
  11.             System.out.println(list.get(i));
  12.         }
  13.     }
  17.         public static ArrayList<String> Permutation(String str) {
  18.             if (str == null || str.equals("")) {
  19.                 return res;
  20.             }
  21.             char[] strs = str.toCharArray();
  22.             Arrays.sort(strs);
  23.             visited = new boolean[strs.length];
  24.             combination(strs, 0);
  25.             res.addAll(paths);
  26.             return res;
  27.         }
  29.         private static void combination(char[] strs, int len) {
  30.             if (len == strs.length) {
  31.                 paths.add(path.toString());
  32.                 return;
  33.             }
  34.             for (int i = 0; i < strs.length; i++) {
  35.                 if (!visited[i]) {
  36.                     visited[i] = true;
  37.                     path.append(strs[i]);
  38.                     combination(strs, len + 1);
  39.                     //Duang ~ 回溯 - 状态重置
  40.                     visited[i] = false;
  41.                     path.deleteCharAt(path.length() - 1);
  42.                 }
  43.             }
  44.         }
  45. }