On considère dans cet exercice des « mots » comptant au moins une lettre. Ces « mots » n'existent pas nécessairement dans le dictionnaire.
On n'utilise que des lettres en casse majuscule et non accentuées.
Les anagrammes d'un mot sont tous les mots que l'on peut écrire en utilisant les mêmes lettres. Là encore, les anagrammes ne sont pas nécessairement dans le dictionnaire.
Voici par exemple les premiers anagrammes de "GALA" :
Anagramme
Rang
"AAGL"
1
"AALG"
2
"ALAG"
3
"ALGA"
4
"AGAL"
5
"AGLA"
6
"GAAL"
7
"GALA"
8
...
...
Répétitions
Dans le cas où le mot compte plusieurs fois la même lettre on n'écrit qu'une seule fois les anagrammes correspondants. Par exemple, "ABA" ne compte que 3 anagrammes : "AAB", "ABA" et "BAA".
On peut associer à chaque anagramme son rang dans la liste triée dans l'ordre alphabétique de tous les anagrammes du mot. Ainsi, le rang de "GALA" est 8.
On demande d'écrire une fonction rang qui prend en argument une chaîne de caractères mot et renvoie son rang.
Attention
Il est possible de déterminer le rang d'un mot en énumérant tous les anagrammes dans l'ordre alphabétique mais cette version devient rapidement très longue à exécuter.
Par exemple, le rang de "ENUMERATION" est 1 971 860 !
Faites quelques essais. Avec "RANG" et "SARAH" par exemple...
Astuce (2)
La liste triée des anagrammes de "SARAH" contient tout d'abord les anagrammes débutant par "A", puis ceux débutant par "H"etc
Astuce (3)
Le nombre d'anagrammes d'un mot de \(N\) lettres dans lequel chaque lettre est répétée \((n_0, n_1, ...,n_k)\) fois (\(n_0+ n_1+ ...+n_k = N\)) est égal à :
On rappelle que \(N! = N\times (N-1)\times (N-2)\times ...\times 1\). On convient si besoin que \(0!=1\).
Astuce (4)
On peut utiliser un code récursif. Si l'on souhaite déterminer le rang d'un mot, il faut déjà compter le nombre d'anagrammes débutant par une lettre placée plus tôt dans l'alphabet puis lui ajouter le rang du mot privé de sa première lettre.
Le rang de "SARAH" est par exemple égal :
au nombre d'anagrammes débutant par "A", par "H" et par "R",
additionné au rang de "ARAH".
Un mot de une lettre a toujours un rang égal à 1 !
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)