Rang d'un anagramme⚓︎
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 !
Exemples
>>> rang("GALA")
8
>>> rang("BCA")
4
>>> rang("ENUMERATION")
1971860
def rang(mot):bksl-nl ...bksl-nlbksl-nlbksl-nl# Testsbksl-nlassert rang("GALA") == 8, "Erreur sur le rang de GALA"bksl-nlassert rang("BCA") == 4, "Erreur sur le rang de BCA"bksl-nlassert rang("ABAACAC") == 32, "Erreur sur le rang de ABAACAC"bksl-nlassert rang("ENUMERATION") == 1971860, "Erreur sur le rang de ENUMERATION"bksl-nlbksl-nldef occurrences(mot):bksl-nl decomptes = {}bksl-nl for lettre in mot:bksl-nl if lettre in decomptes:bksl-nl decomptes[lettre] += 1bksl-nl else:bksl-nl decomptes[lettre] = 1bksl-nl return decomptesbksl-nlbksl-nlbksl-nldef factorielle(n):bksl-nl if n == 0:bksl-nl return 1bksl-nl return n py-str factorielle(n - 1)bksl-nlbksl-nlbksl-nldef multinomial(n, repetitions):bksl-nl coeff = factorielle(n)bksl-nl for x in repetitions:bksl-nl coeff //= factorielle(x)bksl-nl return coeffbksl-nlbksl-nlbksl-nldef rang(mot):bksl-nl if len(mot) == 1:bksl-nl return 1bksl-nlbksl-nl longueur = len(mot)bksl-nl decomptes = occurrences(mot)bksl-nl presentes = [lettre for lettre in decomptes]bksl-nl lettrespy-undtriees = sorted(presentes)bksl-nl total = 0bksl-nl i = 0bksl-nl while lettrespy-undtriees[i] != mot[0]:bksl-nl debut = lettrespy-undtriees[i]bksl-nl repetitions = []bksl-nl for lettre in presentes:bksl-nl if lettre != debut:bksl-nl repetitions.append(decomptes[lettre])bksl-nl else:bksl-nl repetitions.append(decomptes[lettre] - 1)bksl-nl total += multinomial(longueur - 1, repetitions)bksl-nl i += 1bksl-nl return total + rang(mot[1:])bksl-nlbksl-nlbksl-nl# Testsbksl-nlassert rang("GALA") == 8, "Erreur sur le rang de GALA"bksl-nlassert rang("BCA") == 4, "Erreur sur le rang de BCA"bksl-nlassert rang("ABAACAC") == 32, "Erreur sur le rang de ABAACAC"bksl-nlassert rang("ENUMERATION") == 1971860, "Erreur sur le rang de ENUMERATION"bksl-nlbksl-nl
A
Commentaires⚓︎
{{ IDE('exo_corr') }}
On organise le code en plusieurs fonctions :
-
occurrences
compte le nombre d'occurrences de chaque lettre dansmot
. On peut utiliser le résultat afin de lister les lettres présentes dansmot
: ce sont les clés du dictionnaire. -
factorielle
renvoie la factorielle d'un entier positifn
. On utilise le cas de basen == 0
pour simplifier le calcul dans la fonctionmultinomial
. -
multinomial
calcule le nombre de permutations d'un ensemble den
éléments, en tenant compte des répétitions fournies dansrepetitions
.Si une des valeurs de
repetition
vaut0
, la convention 0!=1 permet de tout de même calculer le résultat.
Coefficient multinomial
Le nombre de permutations calculé par la fonction précédente est appelé coefficient multinomial en mathématiques.
-
rang
calcule la valeur cherchée : -
On commence par déterminer les occurrences de chaque lettre dans
mot
(decomptes
). - Les clés de ce dictionnaire nous indique les lettres présentes dans la chaîne.
- On trie cette liste et on la parcourt jusqu'à rencontrer la première lettre de
mot
. - Pour chaque lettre lue précédent mot, on compte le nombre d'anagrammes commençant par cette lettre. Il s'agit du nombre de permutations de
longueur - 1
éléments, chacun étant répété autant de fois que nécessaire (sauf pour la lettre lue qui est répétée une fois de moins) - Une fois le parcours effectué on somme le total avec le rang du mot privé de sa première lettre.
Z
Astuce (1)
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 !