chaîne plus rapide permutation

Question

J'ai des méthodes de permutation

public void permute(String str) { 
    permute(str.toCharArray(), 0, str.length() - 1); 
} 

private void permute(char[] str, int low, int high) { 
    if (low == high) { 
     writeIntoSet(new String(str, 0, length)); 
    } else { 
     for (int i = low; i <= high; i++) { 
      char[] x = charArrayWithSwappedChars(str, low, i); 
      permute(x, low + 1, high); 
     } 
    } 
} 

private char[] charArrayWithSwappedChars(char[] str, int a, int b) { 
    char[] array = str.clone(); 
    char c = array[a]; 
    array[a] = array[b]; 
    array[b] = c; 
    return array; 
} 

Mais quand je mets la chaîne, ce qui est une longueur de 10 lettres dans cette méthode, il fait 10! combinaisons et cela prend tellement de temps. Est-il possible de le rendre plus rapide?

EDIT

je dois faire des permutations de 10 lettres, mais après cela, je recherche ces "mots" dans le dictionnaire. Par exemple, j'ai - CxRjAkiSvH et j'ai besoin de mots CAR, CARS, CRASH, etc. Y at-il une option de performance?

Answer 1

Il existe des algorithmes pour générer des permutations qui peuvent être légèrement plus efficaces que celui que vous utilisez, vous pouvez donc jeter un oeil à one of those. J'ai utilisé l'algorithme de Johnson-Trotter dans le passé, ce qui permet une légère accélération en rendant le changement minimum possible pour obtenir la permutation suivante à chaque fois. Je ne sais pas quel genre de contraintes vous devez respecter, mais si vous n'avez pas besoin d'utiliser Java, mieux vaut ne pas le faire. Ce ne sera tout simplement pas le plus rapide pour cela. Surtout si votre algorithme utilise la récursivité. Comme quelqu'un d'autre l'a suggéré, si vous respectez cet algorithme, il vaut mieux vous éloigner de l'approche récursive et essayer d'utiliser une boucle.

Answer 2

Pour une chaîne de 10 caractères, il y en a 10! permutations, il n'y a pas deux façons de contourner cela. Vous pourriez être en mesure de le rendre légèrement plus rapide en ajoutant à la place StringBuffer s, ou en utilisant un char[] manuellement.