//字符串全排列

package com.demo.acm;

public class AllSortChar {

    public static void allSort(char[] buf,int start,int end){
        if(start==end){
            for(int i=0;i<=end;i++){
                System.out.print(buf[i]);
            }
            System.out.println();
        }else{
            //多个字母全排列
            for(int i=start;i<=end;i++){
                char tmp=buf[start];//交换数组的第一个元素与后续的元素
                buf[start]=buf[i];
                buf[i]=tmp;
                allSort(buf,start+1,end);//后续元素递归全排列
                tmp=buf[start];//将交换后的数组还原
                buf[start]=buf[i];
                buf[i]=tmp;
            }
        }
    }
    public static void main(String[] args){
        String test="abcd";
        char[] chars=test.toCharArray();
        allSort(chars, 0, chars.length-1);
    }
}

//没有重复元素的排列
public class Solution {
    public ArrayList<ArrayList<Integer>> permute(int[] num) {
        ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();

        if (null == num || num.length == 0)
            return result;
        int length = num.length;
        if (length == 1) {
            ArrayList<Integer> tmp = new ArrayList<Integer>();
            tmp.add(num[0]);
            result.add(tmp);
            return result;
        }
        ArrayList<Integer> arrayList = null;
        allPermutations(num, result,arrayList);
        return result;
    }
    private void allPermutations(int[] num,
            ArrayList<ArrayList<Integer>> result, ArrayList<Integer> arrayList) {
        // TODO Auto-generated method stub
        Arrays.sort(num);
        int length = num.length;
        int tmp;
        while(true){
            arrayList=new ArrayList<Integer>();
            for(int i=0;i<length;i++)
                arrayList.add(num[i]);
            result.add(arrayList);
            int i;
            for(i=length-1;i>0;i--){
                if(num[i]>num[i-1]){
                    break;
                }
            }
            if(i<=0)
                break;
            int k;
            for(k=i;k<length;k++){
                if(k==length-1){
                    break;
                }
                if(num[k]>num[i-1]&&num[k+1]<num[i-1]){
                    break;
                }
            }
            tmp=num[i-1];
            num[i-1]=num[k];
            num[k]=tmp;
            sortArrays(num, i, length-1);
        }
    }
    private void sortArrays(int[] num,int i,int j){
        int beg=i;
        int end=j;
        int tmp;
        while(beg<end){
            tmp=num[beg];
            num[beg]=num[end];
            num[end]=tmp;
            beg++;
            end--;
        }
    }