剑指Offer(28)-字符串的全排列

题目：

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

输入描述:

输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

方法一：递归算法：

我们将字符串看成两部分组成，第一部分为它的第一个字符，第二部分为后面所有的字符。首先求所有可能出现再第一个位置的字符，即把第一个字符与后面所有的字符进行交换。当固定完第一个字符后，在将剩余的字符串分为两部分，继续固定第一个字符。
如果里面有重复值呢？由于全排列是从第一个字符开始的，每个数分别与后面的字符进行交换，比如abb，假如第一个字符与第二个字符进行交换了，那么实际上不需要第一个字符在于第三个字符进行交换。

代码实现：

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Collections;
public class Solution {
    private void swap(char[] ch,int i,int j){
        char tmp=ch[i];
        ch[i]=ch[j];
        ch[j]=tmp;
    }
    private void per(char[] ch,int index,ArrayList list){
        if(index==ch.length-1){
            list.add(String.valueOf(ch));
            return ;
        }
        HashSet<Character> set=new HashSet();
        for(int i=index;i<ch.length;i++){
            //如果最后一位确定的值重复出现，不进行递归。
           if(!set.contains(ch[i])){
               //本次递归次字符第一次与index交换，加入去重集合。
               set.add(ch[i]);
               //交换进行下次递归
               swap(ch,index,i);
               per(ch,index+1,list);
               //下次递归完，回到本层，恢复原来排序
               swap(ch,i,index);
           } 
        }
    }
    public ArrayList<String> Permutation(String str) {
       if(str==null||str.length()==0){
           return new ArrayList<String>();
       }
       ArrayList<String> list=new ArrayList();
       //list.add(str);
       per(str.toCharArray(),0,list);
        //按字典进行排序
        Collections.sort(list);
        return list;
        
    }
}

方法二： 字典序列排序算法：

一个全排列可以看做一个字符串，字符串有前缀，后缀。
生成一个全排列的下一个排列，就是两个排列之间在没有其它排列。这就要求两个排列之间有尽可能多的相同前缀。
如：1-9的全排列最小为123456789；最大为987654321。 从右向左扫描都是递增的，那么就没有下一个更大的全排列了。
如何找到下一个全排列： 346987521的下一个：

1. 从后往前找到一个不递增的位置 p(i-1)<p(i)
   346 < 987521
   找到6是第一个变小的数字
2. 从i位置往后找，找到最后一个大于6的数；
   346 < 98 <7 521 找到了7。
3. 交换i-1和7 的位置。
4. 倒序i位置后所有数据。
   其实就是，想找到当前下一个大的全排序，那么就先找到从后往前第一个非递增的数，那么包括它的字符前缀找不到更大全排序，那么只能以它前面的字符串作为前缀进行寻找，此时我们只要找到后缀中最小的比它大的数就是i的值。交换两个数，此时只需要将后缀变为最小全排列均可。又因为后缀此时是递减的，只需要将其反转便可得到递增的最小全排列。

代码实现：

import java.util.ArrayList;
import java.util.Arrays;
public class Solution {
    private void swap(char[] ch,int a,int b){
        char tmp=ch[a];
        ch[a]=ch[b];
        ch[b]=tmp;
    }
    //倒序指定位置
    private void reverse(char[] ch,int l,int r){
        while(l<r){
            swap(ch,l++,r--);
        }
    }
    public ArrayList<String> Permutation(String str) {
         ArrayList<String> list=new ArrayList();
        if(str==null||str.length()==0)
            return list;
        char[] ch=str.toCharArray();
        //排序
        Arrays.sort(ch);
        //当前就是最小的全排序
        list.add(String.valueOf(ch));
        int len=ch.length;
        while(true){
            int l=len-1;
            //找到第一个非递增的字符。
            while(l>=1&&ch[l-1]>=ch[l]){
                l--;
            }
            //若没有则说明已是最大，直接跳出
            if(l==0)
                break;
            int r=l;
            //找到最后一个大于ch[l-1]的字符
            while(r<len && ch[l-1]<ch[r]){
                r++;
            }
            r--;
            //int r=len;
            //while(r>l&&ch[l-1]>ch[r]){
           //     r--;
            //}
            //交换i-1和r,
            swap(ch,l-1,r);
            //对l以及l后数据重排序
            reverse(ch,l,len-1);
            list.add(String.valueOf(ch));
        }
        return list;
    }
}