La méthode de l'ordre du dictionnaire consiste à générer tous les arrangements un par un selon l'idée du tri du dictionnaire.
En mathématiques, l'ordre du dictionnaire ou du dictionnaire (également connu sous le nom d'ordre de vocabulaire, de l'ordre du dictionnaire, de l'ordre alphabétique ou de l'ordre du dictionnaire) est une méthode d'ordre alphabétique dans lequel les mots ont organisé alphabétique basé sur l'ordre alphabétique. Cette généralisation réside principalement dans la définition de l'ordre total des séquences (souvent appelées mots en informatique) des éléments qui définissent un ensemble d'éléments complètement ordonné ordonné (souvent appelé alphabet).
Pour la disposition des nombres 1, 2, 3 ... n, la séquence de différentes arrangements est déterminée en comparant la séquence de nombres correspondants un par un de gauche à droite. Par exemple, pour les arrangements 12354 et 12345 des 5 nombres, l'arrangement 12345 est devant et l'arrangement 12354 est à l'arrière. Selon ce règlement, le premier parmi tous les arrangements des 5 nombres est de 12345 et le dernier est 54321.
Par exemple, toutes les dispositions composées de 1, 2, 3, de petites à grandes sont:
123,132,213,231,312,321
Toutes les arrangements composés de 1, 2, 3, 4:
1234, 1243, 1324, 1342, 1423, 1432,
2134, 2143, 2314, 2341, 2413, 2431,
3124, 3142, 3214, 3241, 3412, 3421,
4123, 4132, 4213, 4231, 4312, 4321.
Premièrement, une séquence de caractères dans le jeu de caractères donné doit être spécifiée, et sur cette base, chaque arrangement est généré en séquence.
[Exemple] Set de caractères {1,2,3}, les nombres plus petits sont les premiers, donc l'arrangement complet généré dans l'ordre du dictionnaire est: 123, 132, 213, 231, 312, 321.
Générez la permutation suivante étant donné une permutation complète, et la soi-disant suivante est la chaîne adjacente à la suivante sans ordre de dictionnaire. Cela nécessite que celui-ci ait le même préfixe que le prochain aussi longtemps que possible, c'est-à-dire que la variation est limitée au suffixe le plus court possible.
Il existe une certaine relation entre ce dernier arrangement et l'arrangement précédent. Le processus de solution de ce dernier arrangement est le suivant:
Avec l'arrangement (P) = 2763541, trié par dictionnaire, quel est son prochain arrangement?
2763541 (Trouvez le dernier ordre positif 35)
2763541 (Trouvez le dernier numéro 4 après 3 et est supérieur à 3)
2764531 (commutateur 3, 4 positions)
2764135 (Invert 5, 3, 1 après 4)
Ce qui suit est une description du prochain arrangement de p [1… n]:
Trouver i = max {j | p [j 1] <p [j]} (trouver le dernier ordre positif)
Trouver j = max {k | p [i 1] <p [k]} (trouvez le dernier plus grand que p [i 1])
Échange p [i 1] et p [j] pour obtenir p [1]… p [i-2] p [j] p [i] p [i + 1]… p [j-1] p [i-1] p [j + 1]… p [n]
Inverser le nombre après p [j] pour obtenir p [1]… p [i-2] p [j] p [n]… p [j + 1] p [i-1] p [j-1]… p [i]
L'implémentation du code est la suivante:
privé static int [] getpermutation (int [] in) {int [] ns = in; int basction = -1; for (int i = nshength-1; i> = 1; i--) {if (ns [i-1] <ns [i]) {base = i-1; break;}} // il a été organisé à la dernière et à la borde i = ns.length-1; i> = base; i--) {if (ns [i]> ns [base]) {bigrise = i; bris = j; while (gauche <droite) {swap (ns, gauche, droite); gauche ++; droite -;}} échange de void statique privé (int [] ns, int, int plus grand) {int temp = ns [base]; ns [base] = ns [plus grand]; ns [plus grand] = temp;}Résumer
Ce qui précède est tout au sujet de l'analyse de l'algorithme de tri du dictionnaire en langue Java et des exemples de code. J'espère que ce sera utile à tout le monde. Les amis intéressés peuvent continuer à se référer à d'autres sujets connexes sur ce site. S'il y a des lacunes, veuillez laisser un message pour le signaler. Merci vos amis pour votre soutien pour ce site!