AnalyseNotion · Glossaire
Lexicographique (ordre)
L'ordre lexicographique ordonne des mots ou des n-uplets à partir d'un ordre fixé sur leurs composants : on compare de gauche à droite, et le premier composant différent décide. Si l'un est un préfixe de l'autre, le plus court vient d'abord ; l'ordre obtenu est total si l'ordre de base l'est.
Sommaire
Ce que vous allez apprendre
- Appliquer la règle de la première différence à des mots et à des n-uplets.
- Traiter correctement le cas où un mot est le préfixe d'un autre.
- Distinguer l'ordre lexicographique de l'ordre composante par composante et du classement par longueur.
- Identifier les conditions nécessaires pour obtenir un ordre total.
En clair
Imaginez quatre fiches portant les mots « car », « carte », « carton » et « case ». Pour les ranger, on lit de gauche à droite. Tant que les lettres coïncident, rien n'est décidé. Entre « carte » et « carton », les quatre premières lettres sont les mêmes ; la première différence oppose ensuite e à o, donc « carte » vient avant « carton ».
Si l'un des mots s'arrête alors que tout ce qui précède est identique, le plus court passe d'abord : « car » précède « carte ». L'ordre lexicographique applique ce même geste aux listes de nombres ou à tout autre n-uplet dont les composants possèdent déjà un ordre.
Définition
L'ordre lexicographique compare des suites composant par composant, depuis la première position. Il suppose qu'un ordre de base est fixé sur les composants : l'ordre des lettres pour des mots, ou l'ordre usuel des nombres pour des n-uplets numériques. La comparaison s'arrête à la première position où les deux suites diffèrent ; l'ordre des composants rencontrés à cette position donne alors l'ordre des suites.
Pour deux n-uplets de même longueur, notés x = (x1, …, xn) et y = (y1, …, yn), le critère précis est :
Pour des mots finis de longueurs différentes, il faut aussi traiter le cas où aucun composant différent n'apparaît avant la fin du plus court : un mot qui est le préfixe de l'autre vient avant lui. Si l'ordre de base est total, cette règle fournit un ordre total sur les mots finis : deux mots peuvent toujours être comparés.
Un exemple, pas à pas
On veut ranger les quatre mots « carton », « car », « case » et « carte ». Les données sont les lettres de chaque mot, lues de gauche à droite, avec l'ordre alphabétique usuel sur les lettres.
1. « car » et « carte » ont les mêmes trois premières lettres. Le premier mot s'arrête : « car » vient donc avant « carte ».
2. « carte » et « carton » coïncident jusqu'à la quatrième lettre. À la cinquième position, e vient avant o : « carte » précède « carton ».
3. « carton » et « case » commencent par « ca ». Leur première différence est à la troisième position : r vient avant s, donc « carton » précède « case ».
Le rangement obtenu est « car », « carte », « carton », « case ». Pour le contrôler, on reprend chaque paire voisine : préfixe pour la première, e avant o pour la deuxième, puis r avant s pour la troisième. Chaque comparaison confirme le même ordre.
En pratique
Dans un dictionnaire ou un index de mots, la comparaison lexicographique donne un rangement reproductible : on cherche la première lettre différente. Si l'on veut regrouper d'abord les mots par longueur, un ordre par longueur puis lexicographique est plus adapté.
En informatique, le même principe compare des chaînes ou des listes. Il faut toutefois connaître l'ordre réellement appliqué aux composants : pour du texte, un ordre de caractères choisi par le système peut ne pas reproduire exactement les conventions d'un dictionnaire.
En combinatoire, l'ordre lexicographique sert à énumérer des mots ou des n-uplets sans ambiguïté. Il convient lorsque la première coordonnée est prioritaire. Si plusieurs coordonnées doivent être comparées sans priorité, un ordre composante par composante répond à une autre question.
En algèbre, on peut appliquer la règle aux n-uplets d'exposants pour comparer des termes. Le choix de la première variable devient alors décisif : changer l'ordre des variables peut changer le résultat de la comparaison.
À ne pas confondre
Deux règles voisines peuvent produire un rangement différent, même lorsqu'elles utilisent les mêmes composants.
Ordre composante par composante
L'ordre lexicographique donne la priorité à la première différence. Dans un ordre composante par composante, il faut au contraire que toutes les coordonnées aillent dans le même sens. Ainsi, (1, 5) précède lexicographiquement (2, 3), mais les deux couples ne sont pas comparables composante par composante puisque 1 < 2 et 5 > 3.
Ordre par longueur puis lexicographique
Cette variante classe d'abord les mots selon leur longueur, puis départage ceux de même longueur par l'ordre lexicographique. « case » vient après « carton » dans l'ordre lexicographique, mais avant lui dans un ordre par longueur, car quatre lettres précèdent six lettres.
Limites et pièges
La règle est nette seulement lorsque l'ordre des composants et la convention sur les préfixes sont fixés.
Le préfixe ne fournit aucune première différence
Dans « car » et « carte », toutes les lettres du mot court coïncident avec le début du mot long. Chercher indéfiniment une lettre différente bloque la comparaison. Pour les mots finis, on applique la convention explicite qui place le préfixe avant son prolongement.
L'ordre de base doit être connu
Dire seulement « ranger lexicographiquement » ne fixe pas l'ordre des lettres accentuées, des majuscules ou des symboles. Deux conventions peuvent donc donner deux listes différentes. Il faut annoncer l'alphabet, l'ordre des caractères ou la règle de classement employée.
Un ordre de base partiel ne devient pas total
Si deux composants possibles ne sont pas comparables dans l'ordre de départ, deux mots dont ils forment la première différence peuvent rester incomparables. La conclusion « ordre total » exige donc un ordre de base total ; sinon, il faut accepter une relation partielle ou choisir une règle de départ plus complète.
Pour aller plus loin
L'ordre total précise pourquoi deux éléments quelconques doivent pouvoir être départagés. Cette propriété explique la portée de l'ordre lexicographique lorsque l'ordre choisi pour les composants est lui-même total.
L'analyse combinatoire montre le cadre où un ordre systématique aide à énumérer des mots, des choix ou des configurations sans omission.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres