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

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) + "  ");
    }
}

另一种简单的方法是遍历字符串，选择尚未使用的字符并将其放入缓冲区，继续循环，直到缓冲区大小等于字符串长度。我更喜欢这个回溯跟踪解决方案，因为:

容易理解 容易避免重复 输出是排序的

下面是java代码:

List<String> permute(String str) {
  if (str == null) {
    return null;
  }

  char[] chars = str.toCharArray();
  boolean[] used = new boolean[chars.length];

  List<String> res = new ArrayList<String>();
  StringBuilder sb = new StringBuilder();

  Arrays.sort(chars);

  helper(chars, used, sb, res);

  return res;
}

void helper(char[] chars, boolean[] used, StringBuilder sb, List<String> res) {
  if (sb.length() == chars.length) {
    res.add(sb.toString());
    return;
  }

  for (int i = 0; i < chars.length; i++) {
    // avoid duplicates
    if (i > 0 && chars[i] == chars[i - 1] && !used[i - 1]) {
      continue;
    }

    // pick the character that has not used yet
    if (!used[i]) {
      used[i] = true;
      sb.append(chars[i]);

      helper(chars, used, sb, res);

      // back tracking
      sb.deleteCharAt(sb.length() - 1);
      used[i] = false;
    }
  }
}

str输入:1231

输出列表:{1123,1132,1213,1231,1312,1321,2113,2131,2311,3112,3121,3211}

注意，输出是排序的，没有重复的结果。

/** Returns an array list containing all
 * permutations of the characters in s. */
public static ArrayList<String> permute(String s) {
    ArrayList<String> perms = new ArrayList<>();
    int slen = s.length();
    if (slen > 0) {
        // Add the first character from s to the perms array list.
        perms.add(Character.toString(s.charAt(0)));

        // Repeat for all additional characters in s.
        for (int i = 1;  i < slen;  ++i) {

            // Get the next character from s.
            char c = s.charAt(i);

            // For each of the strings currently in perms do the following:
            int size = perms.size();
            for (int j = 0;  j < size;  ++j) {

                // 1. remove the string
                String p = perms.remove(0);
                int plen = p.length();

                // 2. Add plen + 1 new strings to perms.  Each new string
                //    consists of the removed string with the character c
                //    inserted into it at a unique location.
                for (int k = 0;  k <= plen;  ++k) {
                    perms.add(p.substring(0, k) + c + p.substring(k));
                }
            }
        }
    }
    return perms;
}

递归Python解决方案

def permute(input_str):
    _permute("", input_str)

def _permute(prefix, str_to_permute):
    if str_to_permute == '':
        print(prefix)

    else:
        for i in range(len(str_to_permute)): 
            _permute(prefix+str_to_permute[i], str_to_permute[0:i] + str_to_permute[i+1:])

if __name__ == '__main__':
    permute('foobar')

这是一个具有O(n!)时间复杂度的算法，具有纯递归和直观。

public class words {
static String combinations;
public static List<String> arrlist=new ArrayList<>();
public static void main(String[] args) {
    words obj = new words();

    String str="premandl";
    obj.getcombination(str, str.length()-1, "");
    System.out.println(arrlist);

}


public void getcombination(String str, int charIndex, String output) {

    if (str.length() == 0) {
        arrlist.add(output);
        return ;
    }

    if (charIndex == -1) {
        return ;
    }

    String character = str.toCharArray()[charIndex] + "";
    getcombination(str, --charIndex, output);

    String remaining = "";

    output = output + character;

    remaining = str.substring(0, charIndex + 1) + str.substring(charIndex + 2);

    getcombination(remaining, remaining.length() - 1, output);

}

}

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

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) + "  ");
    }
}