パフォーマンス：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

---

長い答え：

あなたが取得するJavas 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...