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

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;
    }
}
}

使用递归的简单python解决方案。

def get_permutations(string):

    # base case
    if len(string) <= 1:
        return set([string])

    all_chars_except_last = string[:-1]
    last_char = string[-1]

    # recursive call: get all possible permutations for all chars except last
    permutations_of_all_chars_except_last = get_permutations(all_chars_except_last)

    # put the last char in all possible positions for each of the above permutations
    permutations = set()
    for permutation_of_all_chars_except_last in permutations_of_all_chars_except_last:
        for position in range(len(all_chars_except_last) + 1):
            permutation = permutation_of_all_chars_except_last[:position] + last_char + permutation_of_all_chars_except_last[position:]
            permutations.add(permutation)

    return permutations

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

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;
    }
}
}

这是另一个更简单的方法来做一个字符串的排列。

public class Solution4 {
public static void main(String[] args) {
    String  a = "Protijayi";
  per(a, 0);

}

static void per(String a  , int start ) {
      //bse case;
    if(a.length() == start) {System.out.println(a);}
    char[] ca = a.toCharArray();
    //swap 
    for (int i = start; i < ca.length; i++) {
        char t = ca[i];
        ca[i] = ca[start];
        ca[start] = t;
        per(new String(ca),start+1);
    }

}//per

}

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

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]。

//插入每个字符到数组列表中

static ArrayList al = new ArrayList();

private static void findPermutation (String str){
    for (int k = 0; k < str.length(); k++) {
        addOneChar(str.charAt(k));
    }
}

//insert one char into ArrayList
private static void addOneChar(char ch){
    String lastPerStr;
    String tempStr;
    ArrayList locAl = new ArrayList();
    for (int i = 0; i < al.size(); i ++ ){
        lastPerStr = al.get(i).toString();
        //System.out.println("lastPerStr: " + lastPerStr);
        for (int j = 0; j <= lastPerStr.length(); j++) {
            tempStr = lastPerStr.substring(0,j) + ch + 
                    lastPerStr.substring(j, lastPerStr.length());
            locAl.add(tempStr);
            //System.out.println("tempStr: " + tempStr);
        }
    }
    if(al.isEmpty()){
        al.add(ch);
    } else {
        al.clear();
        al = locAl;
    }
}

private static void printArrayList(ArrayList al){
    for (int i = 0; i < al.size(); i++) {
        System.out.print(al.get(i) + "  ");
    }
}