改进的代码相同

    static String permutationStr[];
    static int indexStr = 0;

    static int factorial (int i) {
        if (i == 1)
            return 1;
        else
            return i * factorial(i-1);
    }

    public static void permutation(String str) {
        char strArr[] = str.toLowerCase().toCharArray();
        java.util.Arrays.sort(strArr);

        int count = 1, dr = 1;
        for (int i = 0; i < strArr.length-1; i++){
            if ( strArr[i] == strArr[i+1]) {
                count++;
            } else {
                dr *= factorial(count);
                count = 1;
            }       
        }
        dr *= factorial(count);

        count = factorial(strArr.length) / dr;

        permutationStr = new String[count];

        permutation("", str);

        for (String oneStr : permutationStr){
            System.out.println(oneStr);
        }
    }

    private static void permutation(String prefix, String str) {
        int n = str.length();
        if (n == 0) {
            for (int i = 0; i < indexStr; i++){
                if(permutationStr[i].equals(prefix))
                    return;
            }        
            permutationStr[indexStr++] = prefix;
        } else {
            for (int i = 0; i < n; i++) {
                permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i + 1, n));
            }
        }
    }

其中一个简单的解决方案是使用两个指针继续递归地交换字符。

public static void main(String[] args)
{
    String str="abcdefgh";
    perm(str);
}
public static void perm(String str)
{  char[] char_arr=str.toCharArray();
    helper(char_arr,0);
}
public static void helper(char[] char_arr, int i)
{
    if(i==char_arr.length-1)
    {
        // print the shuffled string 
            String str="";
            for(int j=0; j<char_arr.length; j++)
            {
                str=str+char_arr[j];
            }
            System.out.println(str);
    }
    else
    {
    for(int j=i; j<char_arr.length; j++)
    {
        char tmp = char_arr[i];
        char_arr[i] = char_arr[j];
        char_arr[j] = tmp;
        helper(char_arr,i+1);
        char tmp1 = char_arr[i];
        char_arr[i] = char_arr[j];
        char_arr[j] = tmp1;
    }
}
}

使用递归。

依次尝试每个字母作为第一个字母，然后使用递归调用找到剩余字母的所有排列。 基本情况是，当输入是空字符串时，唯一的排列就是空字符串。

import java.io.*;
public class Anagram {

public static void main(String[] args) {
      java.util.Scanner sc=new java.util.Scanner(System.in);
            PrintWriter p=new PrintWriter(System.out,true);
            p.println("Enter Word");
            String a[],s="",st;boolean flag=true;
            int in[],n,nf=1,i,j=0,k,m=0;
            char l[];
            st=sc.next();
            p.println("Anagrams");
            p.println("1 . "+st);
            l=st.toCharArray();
            n=st.length();
            for(i=1;i<=n;i++){
                nf*=i;
            }

            i=1;
            a=new String[nf];
            in=new int[n];
            a[0]=st;
            while(i<nf){
                for(m=0;m<n;m++){
                    in[m]=n;
                }j=0;
                while(j<n){
                    k=(int)(n*Math.random());

                    for(m=0;m<=j;m++){
                        if(k==in[m]){
                            flag=false;
                            break;          
                        }
                    }
                    if(flag==true){
                        in[j++]=k;
                    }flag=true;
                }s="";
                for(j=0;j<n;j++){
                    s+=l[in[j]];
                }

                //Removing same words
                for(m=0;m<=i;m++){
                        if(s.equalsIgnoreCase(a[m])){
                            flag=false;
                            break;          
                        }
                    }
                    if(flag==true){
                        a[i++]=s;
                        p.println(i+" . "+a[i-1]);
                    }flag=true;

            }

    }
}

使用位操作可以很容易地做到这一点。“我们都知道，任何给定的有N个元素的集合有2N个可能的子集。如果我们用一个位来表示子集中的每个元素呢?位可以是0或1，因此我们可以用它来表示对应的元素是否属于这个给定的子集。所以每个位模式代表一个子集。”(复制文本)

private void getPermutation(String str)
        {
            if(str==null)
                return;
            Set<String> StrList = new HashSet<String>();
            StringBuilder strB= new StringBuilder();
            for(int i = 0;i < (1 << str.length()); ++i)
            {
                strB.setLength(0); //clear the StringBuilder
                for(int j = 0;j < str.length() ;++j){
                    if((i & (1 << j))>0){  // to check whether jth bit is set
                        strB.append(str.charAt(j));
                    }
                }
                if(!strB.toString().isEmpty())
                    StrList.add(strB.toString());
            }
            System.out.println(Arrays.toString(StrList.toArray()));
        }

这就是我通过对排列和递归函数调用的基本理解所做的。虽然要花点时间，但都是独立完成的。

public class LexicographicPermutations {

public static void main(String[] args) {
    // TODO Auto-generated method stub
    String s="abc";
    List<String>combinations=new ArrayList<String>();
    combinations=permutations(s);
    Collections.sort(combinations);
    System.out.println(combinations);
}

private static List<String> permutations(String s) {
    // TODO Auto-generated method stub
    List<String>combinations=new ArrayList<String>();
    if(s.length()==1){
        combinations.add(s);
    }
    else{
        for(int i=0;i<s.length();i++){
            List<String>temp=permutations(s.substring(0, i)+s.substring(i+1));
            for (String string : temp) {
                combinations.add(s.charAt(i)+string);
            }
        }
    }
    return combinations;
}}

生成输出为[abc, acb, bac, bca, cab, cba]。

它背后的基本逻辑是

对于每个字符，将其视为第一个字符，并找出剩余字符的组合。例[abc](abc的组合)->。

a->[bc](a x Combination of (bc))->{abc,acb} b->[ac](b x组合(ac))->{bac,bca} c->[ab](c x Combination of (ab))->{cab,cba}

然后递归地分别调用每个[bc]，[ac]和[ab]。