E11 - Anagrammes⚓︎
Le problème
Proposition 1⚓︎
🐍 Script Python
def Anagrammes(liste_mots:list) -> int:
""" Prend une liste de mots puis recherche et renvoie le nombre de couple d'Anagramme sans compter les doublons
>>> Anagrammes(['le', 'chien', 'marche', 'vers', 'sa', 'niche', 'et', 'trouve', 'une', 'limace', 'de', 'chine', 'nue', 'pleine', 'de', 'malice', 'qui', 'lui', 'fait', 'du', 'charme'])
6
"""
# On retire les doublons
liste_mots = set(liste_mots)
liste_mots = list(liste_mots)
def Trie_mots(liste_mots:list) -> list:
""" Prend chaque mot de la liste les transformes en liste et les trie dans l'odre alphabétique puis les remet dans la liste
>>> Trie_mots(['le', 'chien', 'marche', 'vers', 'sa', 'niche', 'et', 'trouve', 'une', 'limace', 'de', 'chine', 'nue', 'pleine', 'de', 'malice', 'qui', 'lui', 'fait', 'du', 'charme'])
[['e', 'l'], ['c', 'e', 'h', 'i', 'n'], ['a', 'c', 'e', 'h', 'm', 'r'], ['e', 'r', 's', 'v'], ['a', 's'], ['c', 'e', 'h', 'i', 'n'], ['e', 't'], ['e', 'o', 'r', 't', 'u', 'v'], ['e', 'n', 'u'], ['a', 'c', 'e', 'i', 'l', 'm'], ['d', 'e'], ['c', 'e', 'h', 'i', 'n'], ['e', 'n', 'u'], ['e', 'e', 'i', 'l', 'n', 'p'], ['d', 'e'], ['a', 'c', 'e', 'i' , 'l', 'm'], ['i', 'q', 'u'], ['i', 'l', 'u'], ['a', 'f', 'i', 't'], ['d', 'u'], ['a', 'c', 'e', 'h', 'm', 'r']]
"""
liste_mots_trié = []
for x in range(len(liste_mots)):
# On transforme le mot en une liste afin de trier les lettres dans l'odre alphabétique
mot_trié = list(liste_mots[x])
mot_trié.sort()
# On ajoute dans une liste la liste de mot trié
liste_mots_trié.append(mot_trié)
return liste_mots_trié
liste_mots_trié = Trie_mots(liste_mots)
def comptage(liste_mots_trié:list) -> int:
""" Prend une liste et compte le nombre de couple
>>> comptage([['e', 'l'], ['c', 'e', 'h', 'i', 'n'], ['a', 'c', 'e', 'h', 'm', 'r'], ['e', 'r', 's', 'v'], ['a', 's'], ['c', 'e', 'h', 'i', 'n'], ['e', 't'], ['e', 'o', 'r', 't', 'u', 'v'], ['e', 'n', 'u'], ['a', 'c', 'e', 'i', 'l', 'm'], ['d', 'e'], ['c', 'e', 'h', 'i', 'n'], ['e', 'n', 'u'], ['e', 'e', 'i', 'l', 'n', 'p'], ['d', 'e'], ['a', 'c', 'e', 'i' , 'l', 'm'], ['i', 'q', 'u'], ['i', 'l', 'u'], ['a', 'f', 'i', 't'], ['d', 'u'], ['a', 'c', 'e', 'h', 'm', 'r']])
6
"""
nb_Anagrammes = 0
for x in range(len(liste_mots_trié)):
mot = liste_mots_trié[x]
for y in range(x + 1,len(liste_mots_trié)):
if mot == liste_mots_trié[y]:
nb_Anagrammes += 1
return nb_Anagrammes
return comptage(liste_mots_trié)
# tests
import doctest
doctest.testmod()
# Entrée
nb_caractères = int(input())
liste_mots = list(input().split())
# Sortie
print(Anagrammes(liste_mots))
- En snake_case, on commence aussi par une minuscule.
- Faire des doctest plus simple.
- Ici, il vaut mieux faire le
splitdans la fonction. Ça rend surtout les doctest plus simples. - On peut faire un zeste de combinatoire pour compter plus vite les couples.
Proposition 2⚓︎
🐍 Script Python
nombre_caractères = int(input())
liste_mots = input().split(" ")
def sont_des_anagrammes(mot_1, mot_2):
return sorted(mot_1) == sorted(mot_2)
dictionnaire_longueur = dict()
dictionnaire_anagramme = dict()
anagrammes = set()
for mot in liste_mots:
longueur_mot = len(mot)
if longueur_mot not in dictionnaire_longueur:
set_mot = {mot}
dictionnaire_longueur[longueur_mot] = set_mot
else:
dictionnaire_longueur[longueur_mot].add(mot)
for longueur_mot, set_mots in dictionnaire_longueur.items():
if len(set_mots) == 1:
pass
else:
liste_mots = list(set_mots)
for mot_1 in liste_mots:
for mot_2 in liste_mots:
if mot_1 == mot_2:
continue
elif sont_des_anagrammes(mot_1, mot_2):
if mot_1 not in dictionnaire_anagramme:
dictionnaire_anagramme[mot_1] = {mot_2}
else:
dictionnaire_anagramme[mot_1].add(mot_2)
if mot_2 not in dictionnaire_anagramme:
dictionnaire_anagramme[mot_2] = {mot_1}
else:
dictionnaire_anagramme[mot_2].add(mot_1)
def calcul_anagrammes():
"""
Permet de calculer le nombre d'anagrammes dans la phrases et retourne leur nombre
"""
déjà_vu = set()
dictionnaire_anagramme_trié = sorted(dictionnaire_anagramme.items())
for key, value in dictionnaire_anagramme_trié:
for mot in value:
if (mot, key) in déjà_vu:
continue
déjà_vu.add((key, mot))
return len(déjà_vu)
print(calcul_anagrammes())
- Il faut éviter les
continuesi possible. On peut facilement créer une fonction et un retour prématuré. - Les
if cond: pass; else action()se simplifient facilement. On teste la condition contraire et on obtientif not(cond): action().
Proposition 3⚓︎
🐍 Script Python
# Entrée
anagramme = []
anagrammes = {}
texte = input().split()
for mots in texte:
mot = ''.join(sorted(mots))
if mot in anagrammes:
anagrammes[mot].append(mots)
else:
anagrammes[mot] = [mots]
for i in anagrammes:
if len(anagrammes[i]) > 1:
anagramme.append(i)
print(len(anagramme))
print(anagrammes)
# Ne donne pas le bon résultat...
- Bon début, la signature est correcte.
Proposition 4⚓︎
🐍 Script Python
def anagrammes(phrase, nb_anagrammes: int):
""" cherche le nombre d'anagrammes qui existe dans la phrase
"""
phrase1 = []
phrase2 = []
phrase.sort()
phrase = sorted(phrase, key= len)
for x in range(len(phrase) - 1):
if len(phrase[x]) == len(phrase[x + 1]):
if phrase[x] != phrase[x + 1]:
for y in phrase[x]:
phrase1.append(y)
phrase1.sort()
for y in phrase[x + 1]:
phrase2.append(y)
phrase2.sort()
if phrase1 == phrase2:
nb_anagrammes += 1
return nb_anagrammes
nb_caractère = int(input())
phrase = input().split()
nb_anagrammes = 0
print(anagrammes(phrase, nb_anagrammes))
"je voie pas où est le problème"
- Le code est très peu clair. Il faut reprendre des exercices plus simples et s'entrainer à les rendre plus clairs. On a le droit de refaire des exercices déjà résolus ; on progresse encore !
Proposition 5⚓︎
🐍 Script Python
# 0- Coeur du programme
def nombres_anagrammes(nb_caractères: int, chaine_mots: str) -> int:
""" Détermine combien de couples d'anagrammes on peut former à partir des mots de chaine_mot et renvoie le nombre
>>> nombres_anagrammes(11, ["Hello", "World"])
0
>>> nombres_anagrammes(103, ["le", "chien", "marche", "vers", "sa", "niche", "et", "trouve", "une", "limace", "de", "chine", "nue", "pleine", "de", "malice", "qui", "lui", "fait", "du", "charme"])
6
"""
liste_mots = list()
compteur = 0 # On initialise le compteur à 0
for mot in chaine_mots: # On retire les doublons de la chaine et plaçons les mots dans liste_mots
if mot not in liste_mots:
liste_mots.append(mot)
longueur_liste = len(liste_mots)
for x in range(longueur_liste): # Pour chaque mot de liste_mot, on converti le mot en un dictionnaire de lettres
mot = liste_mots[x]
dico = dict()
for lettre in mot: # Pour chaque lettre, on crée la lettre (initialisé à 1) si elle n'existe pas, sinon, on rajoute 1 au dictionnaire de la lettre
dico[lettre] = 1 if lettre not in dico else dico[lettre] + 1
liste_mots[x] = dico # Puis, on met le dictionnaire dans liste_mots à la place du mot
for x in range(longueur_liste): # Enfin, pour chaque dictionnaire, on regarde, si un autre est identique
for y in range(x+1, longueur_liste):
if liste_mots[x] == liste_mots[y]:
compteur += 1 # Si oui, on ajoute 1 au compteur (on ne compte pas 2 fois les mêmes anagrammes)
return compteur # On renvoie le compteur
# 1- Tests
import doctest
doctest.testmod()
# 2- Lecture des entrées
nb_caractères = int(input())
chaine_mots = input().split()
# 3- Appel de la fonction / Sortie
print(nombres_anagrammes(nb_caractères, chaine_mots))
- Il y a plus facile pour avoir une signature de l'anagramme.
- Plutôt qu'un dictionnaire qui compte le nombre de lettres, l'anagramme avec les lettres rangées dans l'ordre alphabétique est une bonne signature ; plus simple à stocker, et pour comparer également.
- Reprendre cette idée en exercice, mais sans dictionnaire.
- L'annotation de type n'est pas bonne ici. Il était plus simple de faire le
splitdans la fonction, et de passer la phrase entière. compteurdoit pouvoir être renommé en plus explicite. De même, essayer de bannir les identifiants nommés d'après leur type.- Un bon éditeur de code indique avec un survol de souris le type d'une variable, et ne propose que les méthodes associées à l'objet.
- On se concentre sur le signifiant d'une variable. Le plus explicite possible.
Proposition 6⚓︎
🐍 Script Python
def nb_anagramme(texte : str) :
""" Renvoie le nombre de couples d'anagrammes formés à partir des mots de la chaine.
>>> texte = 'le chien marche vers sa niche et trouve une limace de chine nue pleine de malice qui lui fait du charme'
>>> nb_anagramme(texte)
6
"""
stock = []
parallèle = []
for mot in texte :
contenu = sorted(list(mot))
stock.append(contenu)
#écriture fonctionnelle syntaxiquement incorrecte mais intention :
#compteur si couple anagramme = doublon de contenu du mot :
#return sum(1 for élément in stock if élément in parallèle else parallèle.append(élément))
somme = 0
for élément in stock :
if élément not in parallèle :
parallèle.append(élément)
else :
somme += 1
return somme
# tests
import doctest
doctest.testmod()
# Entrée
nb_caractères = int(input())
assert 1 <= nb_caractères <= 200
texte = input().split()
# Sortie
print (nb_anagramme(texte))
- Bon début.
Corrigé du professeur⚓︎
Version avec set et dict⚓︎
🐍 Script Python
"""
author: Franck CHAMBON
problem: https://prologin.org/train/2003/semifinal/anagrammes
"""
def signature(mot: str) -> str:
"""Renvoie le mot avec les lettres rangées
dans l'ordre alphabétique.
Ainsi deux anagrammes ont la même signature.
>>> signature("azeerty")
'aeertyz'
"""
mot = list(mot)
mot.sort()
return "".join(mot)
def nb_couples_anagrammes(phrase: str) -> int:
"""Renvoie le nombre de couples d'anagrammes formés
à partir des mots de la chaine.
>>> p_debut = "le chien marche vers sa niche et trouve une limace d"
>>> p_fin = "e chine nue pleine de malice qui lui fait du charme"
>>> phrase = p_debut + p_fin
>>> nb_couples_anagrammes(phrase)
6
"""
mots = set(phrase.split()) # sans doublon
anagrammes = dict()
for mot in mots:
signe = signature(mot)
if signe in anagrammes:
anagrammes[signe] += 1
else:
anagrammes[signe] = 1
nb_couples = 0
for signe in anagrammes:
q = anagrammes[signe] # q comme quantité
# ajout de nb_façons de choisir 2 éléments parmi q.
nb_couples += q * (q-1) // 2
return nb_couples
import doctest
doctest.testmod()
taille = int(input())
phrase = input()
print(nb_couples_anagrammes(phrase))
- On compte ici les couples d'anagrammes de manière efficace.
- On utilise une formule mathématique : le nombre de façons de choisir \(2\) objets parmi \(q\) est \(\dfrac{q(q-1)}2\).
- On utilise ici les facilités de Python, à savoir les ensembles (hors programme) et les dictionnaires.
- On donne ensuite une version sans ça.
Exercice 1 : Dans le cours, reprendre la classe ABR, ou bien Tas, et ajouter sans doublon les mots. Nous n'avons plus besoin de set ici.
Exercice 2 : De même, construire une structure (sans doublon de signature) avec des tuples (signature, effectif) comme éléments. Pour chaque nouveau mot unique, trouver sa signature, le chercher dans votre structure. S'il est absent, ajouter un nœud (signature, 1). S'il est présent, incrémenter son effectif. Nous n'avons plus besoin de dict ici.
Exercice 3 : Proposer une autre méthode pour la signature sans utiliser de tri.
Version sans set ni dict⚓︎
Bientôt... Mais d'abord, à vous !!!