以下是我在《破解编程面试》(P54)一书中提出的解决方案:

/**
 * List permutations of a string.
 * 
 * @param s the input string
 * @return  the list of permutations
 */
public static ArrayList<String> permutation(String s) {
    // The result
    ArrayList<String> res = new ArrayList<String>();
    // If input string's length is 1, return {s}
    if (s.length() == 1) {
        res.add(s);
    } else if (s.length() > 1) {
        int lastIndex = s.length() - 1;
        // Find out the last character
        String last = s.substring(lastIndex);
        // Rest of the string
        String rest = s.substring(0, lastIndex);
        // Perform permutation on the rest string and
        // merge with the last character
        res = merge(permutation(rest), last);
    }
    return res;
}

/**
 * @param list a result of permutation, e.g. {"ab", "ba"}
 * @param c    the last character
 * @return     a merged new list, e.g. {"cab", "acb" ... }
 */
public static ArrayList<String> merge(ArrayList<String> list, String c) {
    ArrayList<String> res = new ArrayList<>();
    // Loop through all the string in the list
    for (String s : list) {
        // For each string, insert the last character to all possible positions
        // and add them to the new list
        for (int i = 0; i <= s.length(); ++i) {
            String ps = new StringBuffer(s).insert(i, c).toString();
            res.add(ps);
        }
    }
    return res;
}

字符串"abcd"的运行输出:

第一步:合并[a]和b: [ba, ab] 步骤2:Merge [ba, ab]和c: [cba, bca, bac, cab, acb, abc] 第三步:Merge [cba, bca, bac, cab, acb, abc]和d: [dcba, cdba, cbad, cbca, bdcad

这里有一个优雅的，非递归的O(n!)解:

public static StringBuilder[] permutations(String s) {
        if (s.length() == 0)
            return null;
        int length = fact(s.length());
        StringBuilder[] sb = new StringBuilder[length];
        for (int i = 0; i < length; i++) {
            sb[i] = new StringBuilder();
        }
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            int times = length / (i + 1);
            for (int j = 0; j < times; j++) {
                for (int k = 0; k < length / times; k++) {
                    sb[j * length / times + k].insert(k, ch);
                }
            }
        }
        return sb;
    }

下面是一个简单的Java递归解决方案:

public static ArrayList<String> permutations(String s) {
    ArrayList<String> out = new ArrayList<String>();
    if (s.length() == 1) {
        out.add(s);
        return out;
    }
    char first = s.charAt(0);
    String rest = s.substring(1);
    for (String permutation : permutations(rest)) {
        out.addAll(insertAtAllPositions(first, permutation));
    }
    return out;
}
public static ArrayList<String> insertAtAllPositions(char ch, String s) {
    ArrayList<String> out = new ArrayList<String>();
    for (int i = 0; i <= s.length(); ++i) {
        String inserted = s.substring(0, i) + ch + s.substring(i);
        out.add(inserted);
    }
    return out;
}

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

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 static void permutation(String str) { 
    permutation("", str); 
}

private static void permutation(String prefix, String str) {
    int n = str.length();
    if (n == 0) System.out.println(prefix);
    else {
        for (int i = 0; i < n; i++)
            permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n));
    }
}

(通过Java编程入门)

使用Es6的字符串排列

使用reduce()方法

Const排列= STR => { If (str.length <= 2) 返回str.length === 2 ?[str, str[1] + str[0]]: [str]; 返回str .split (") .reduce ( (acc, letter, index) => acc.concat(排列(str。Slice (0, index) + str.slice(index + 1))。Map (val =>字母+ val))， ［］ ）; }; console.log(排列(STR));