生成给定字符串的所有排列 [英] Generating all permutations of a given string

问题描述

找到一个字符串的所有排列的优雅方法是什么?例如.ba 的置换，将是 ba 和 ab，但是对于诸如 abcdefgh 这样的更长的字符串呢?有没有Java实现的例子?

What is an elegant way to find all the permutations of a string. E.g. permutation for ba, would be ba and ab, but what about longer string such as abcdefgh? Is there any Java implementation example?

推荐答案

这是我的解决方案，基于《破解编码面试》(P54)一书的想法:

Here is my solution that is based on the idea of the book "Cracking the Coding Interview" (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"的输出:

---

Running output of string "abcd":

• 步骤 1:合并 [a] 和 b:[ba, ab]

• Step 1: Merge [a] and b: [ba, ab]

第 2 步:合并 [ba, ab] 和 c:[cba，bca，bac，cab，acb，abc]

Step 2: Merge [ba, ab] and c: [cba, bca, bac, cab, acb, abc]

第三步:合并[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]

Step 3: Merge [cba, bca, bac, cab, acb, abc] and 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]

这篇关于生成给定字符串的所有排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！