Производительность: Перестановка 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 для перестановки

O (N!) Является худшим временем сложности я могу себе представить. Вы не можете найти более эффективный способ обработки перестановок. Для получения дополнительной информации см:

Stackoverflow-Wiki

Big-O

---

Длинный ответ:

Вы можете улучшить свой код (а не алгоритм) с помощью Javas StringBuffer -класса, чтобы получить более быстрые результаты.

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