package str;

import java.util.ArrayList;

import java.util.Collections;

import java.util.Iterator;

public class StrPermutation {

    public static ArrayList<String> Permutation(String str) {

        if(str==null)

            return new ArrayList<>();

        ArrayList<String> list = new ArrayList<>();

        PermutationCore(str.toCharArray(),0,list);

        ArrayList<String> newList = new ArrayList<>();//去除重复元素,比如aa这种，按我们的方式有aa,aa，但是实质结果只有一个aa

        Iterator<String> it = list.iterator();

        while (it.hasNext())

        {

            String temp = it.next();

            if(!newList.contains(temp))

                newList.add(temp);

        }

        Collections.sort(newList);//字典序排序

        return newList;

    }

    public static void main(String[] args) {

        ArrayList<String> list=  Permutation("abc");

        Iterator<String> it = list.iterator();

        while (it.hasNext())

            System.out.println(it.next());

    }

    public static void PermutationCore(char[] str,int ptr,ArrayList<String> res) {

        //递归的结束条件

        if(ptr==str.length)

        {

            res.add(new String(str));

            return;

        }

        //循环部分

        for(int i = ptr;i<str.length;i++)

        {

            Swap(str,ptr,i);

            PermutationCore(str,ptr+1,res);

            Swap(str,ptr,i);

        }

    }

　　//交换

    public static void Swap(char[] str,int i,int j)

    {

        char temp = str[i];

        str[i] = str[j];

        str[j] = temp;

    }

}