Aller au contenu

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

🐍 Console Python
>>> rang("GALA")
8
>>> rang("BCA")
4
>>> rang("ENUMERATION")
1971860
# 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# Tests supplémentairesbksl-nlfrom math import factorialbksl-nlfrom string import asciipy-unduppercase as ALPHABETbksl-nlfrom random import choice, randrangebksl-nlbksl-nlbksl-nldef rangpy-undcorr(mot):bksl-nl if len(mot) == 1:bksl-nl return 1bksl-nlbksl-nl repetitions = {}bksl-nl for lettre in mot:bksl-nl repetitions[lettre] = repetitions.get(lettre, 0) + 1bksl-nl uniques = set(mot)bksl-nl uniquespy-undtriees = sorted(uniques)bksl-nl total = 0bksl-nl i = 0bksl-nl while uniquespy-undtriees[i] != mot[0]:bksl-nl debut = uniquespy-undtriees[i]bksl-nl denominateur = factorial(repetitions[debut] - 1)bksl-nl for c in uniques - {debut}:bksl-nl denominateur py-str= factorial(repetitions[c])bksl-nl total += factorial(len(mot) - 1) // denominateurbksl-nl i += 1bksl-nl return total + rangpy-undcorr(mot[1:])bksl-nlbksl-nlbksl-nlfor py-und in range(20):bksl-nl taille = randrange(5, 21)bksl-nl mot = "".join([choice(ALPHABET) for py-und in range(taille)])bksl-nl attendu = rangpy-undcorr(mot)bksl-nl assert rang(mot) == attendu, f"Erreur avec {mot}"bksl-nlbksl-nl ∞/∞

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 dans mot. On peut utiliser le résultat afin de lister les lettres présentes dans mot : ce sont les clés du dictionnaire.

  • factorielle renvoie la factorielle d'un entier positif n. On utilise le cas de base n == 0 pour simplifier le calcul dans la fonction multinomial.

  • multinomial calcule le nombre de permutations d'un ensemble de n éléments, en tenant compte des répétitions fournies dans repetitions.

    Si une des valeurs de repetition vaut 0, 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 à :

\[\frac{N!}{n_0!\times n_1!\times ...\times n_k!}\]

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 !

Retour en haut de la page