Performance: JAVA Permutation

Question

So hatte ich diesen Code Permutationen ein Wort zu erzeugen, und speichern Sie es auf ein HashSet für später mit einem Wörterbuch verglichen werden. Aber wenn das Eingabewort 10 oder mehr Buchstaben hat, wird der Permutationsprozess lächerlich langsam. Gibt es neben dem Permutationsalgorithmus Möglichkeiten, die Leistung dieses Prozesses zu verbessern?

/** 
* 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

Die kurze Antwort: (! N) Es gibt keine bessere Komplexität als O für Permutation

O (n!) Ist die schlimmste Zeit-Komplexität kann ich mir vorstellen. Sie können keine effizientere Methode zum Behandeln von Permutationen finden. Für weitere Informationen siehe:

Stackoverflow-Wiki

Big-O

---

Die lange Antwort:

Sie können Ihren Code (nicht Ihr Algorithmus) unter Verwendung von Javas StringBuffer -Klasse verbessern zu erhalten schnellere Ergebnisse.

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; 
} 

Ich habe diesen Code getestet und mit Ihrer alten Methode verglichen. Hier sind meine Ergebnisse.

____________________________________ 
| 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 

Wenn es zu viele Methoden referenzieren Ihre Permutation-Methode sind, ein Wrapper um die optimierte Methode erstellen:

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...