java - 性能:JAVA排列

Question

所以，我用这段代码来生成单词的排列，并将其存储到 HashSet 中，以便稍后与字典进行比较。 但当输入单词有 10 个或更多字母时，排列过程就会变得异常缓慢。除了使用排列算法之外，还有什么方法可以提高这个过程的性能吗？

/**
 * Returns a HashSet of the string permutation.
 *
 * @param prefix an empty string.
 * @param str the string to create perm.
 * @return permutations a HashSet of the permutation.
 */
private static HashSet<String> permutation(String prefix, String str) {
    HashSet<String> permutations = new HashSet<String>();
    int n = str.length();
    if (n == 0) {
        permutations.add(prefix);
    } else {
        for (int i = 0; i < n; i++) {
            permutations.addAll(permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i + 1, n)));
        }
    }
    return permutations;
}

Answer 1

简短回答: 没有比 O(n!) 更复杂的排列

O(n!) 是我能想象到的最糟糕的时间复杂度。您找不到更有效的方法来处理排列。欲了解更多信息，请参阅:

Stackoverflow-Wiki

Big-O

---

长答案:

您可以使用 Java StringBuffer-Class 改进代码(而不是算法)以获得更快的结果。

public static HashSet<StringBuffer> permutationNew(StringBuffer sb_prefix, StringBuffer sb_str) {
    HashSet<StringBuffer> permutations = new HashSet<>();
    int n = sb_str.length();
    if (n == 0) {
        permutations.add(sb_prefix);
    } else {
        for (int i = 0; i < n; i++) {
            permutations.addAll(permutationNew(sb_prefix.append(sb_str.charAt(i)), new StringBuffer(sb_str.substring(0, i)).append(sb_str.substring(i + 1, n))));
        }
    }
    return permutations;
}

我测试了这段代码并将其与您的旧方法进行了比较。这是我的结果。

 ____________________________________
| inputlength | oldmethod | newmethod|
 ------------------------------------
| 1           | 0 ms      | 0 ms     |
| 2           | 0 ms      | 0 ms     |
| 3           | 1 ms      | 0 ms     |
| 4           | 1 ms      | 0 ms     |
| 5           | 2 ms      | 0 ms     |
| 6           | 9 ms      | 3 ms     |
| 7           | 71 ms     | 38 ms    |
| 8           | 400 ms    | 66 ms    |
| 9           | 1404 ms   | 377 ms   |
| 10          | 9696 ms   | 2095 ms  |
L_[...]__________[...]______[...]____J

如果有很多方法引用您的排列方法，请围绕优化方法创建一个包装器:

private static HashSet<String> permutation(String prefix, String str) {
    HashSet<StringBuffer> permutations = permutationNew(new StringBuffer(prefix), new StringBuffer(str);
    //create new HashSet<String> using permutations-HashSet and return it...