生成给定字符串的所有排列

什么是查找字符串所有排列的优雅方式。 例如ba ，会是ba和ab ，但是abcdefgh呢？ 有没有任何Java实现的例子？

---

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编程入门）

---

使用递归。

依次尝试每个字母作为第一个字母，然后使用递归调用查找其余字母的所有排列。

基本情况是当输入是空字符串时，唯一的排列是空字符串。

---

这是我的解决方案，它基于“破解编码访谈”（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”的输出：

步骤1：合并[a]和b：[ba，ab]

步骤2：合并[ba，ab]和c：[cba，bca，bac，cab，acb，abc]

步骤3：合并[cba，bca，bac，cab，acb，abc]和d：[dcba，cdba，cbda，cbad，dbca，bdca，bcda，bcad，dbac，bdac，badc，bacd，dcab，cdab，cadb ，cabd，dacb，adcb，acdb，acbd，dabc，adbc，abdc，abcd]

链接地址: http://www.djcxy.com/p/37291.html

上一篇: Generating all permutations of a given string

下一篇: Algorithm for copying N bits at arbitrary position from one int to another