Correction de Anagrammes

Quelques propositions d'élèves, et à la fin un corrigé du professeur.

• Propositions d'élèves
  • Proposition 1
  • Proposition 2
  • Proposition 3
  • Proposition 4
  • Proposition 5
  • Proposition 6
• Corrigé du professeur
  • Version avec set et dict
  • Version sans set ni dict

Propositions d'élèves

À la suite de chaque proposition de code, un commentaire de correction du professeur. Le cartouche demandé en introduction a été supprimé ici.

Proposition 1

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 simples.
• Ici, il vaut mieux faire le split dans la fonction. Ça rend surtout les doctest plus simples.
• On peut faire un zeste de combinatoire pour compter plus vite les couples.

Proposition 2

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 continue si possible. Ici il suffisait de mieux écrire les tests, en particulier en utilisant des négations.
• Les if cond: pass; else action() se simplifient facilement. On teste la condition contraire et on obtient if not(cond): action().

Proposition 3

# 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

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'entraîner à les rendre plus clairs. On a le droit de refaire des exercices déjà résolus ; on progresse encore !

Proposition 5

# 0- Coeur du programme

def nombres_anagrammes(nb_caractères: int, chaîne_mots: str) -> int:
    """ Détermine combien de couples d'anagrammes on peut former à partir des mots de chaîne_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 chaîne_mots:                 # On retire les doublons de la chaîne 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())
chaîne_mots = input().split()

# 3- Appel de la fonction / Sortie

print(nombres_anagrammes(nb_caractères, chaîne_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 split dans la fonction, et de passer la phrase entière.
• compteur doit 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

def nb_anagramme(texte : str) :
    """ Renvoie le nombre de couples d'anagrammes formés à partir des mots de la chaîne.

    >>> 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

"""
auteur : Franck CHAMBON
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 chaîne.

    >>> p_début = "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_début + p_fin
    >>> nb_couples_anagrammes(phrase)
    6

    """
    mots = set(phrase.split()) # sans doublon

    anagrammes = dict()
    for mot in mots:
        signe = signature(mot)
        if signe not 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 couple d'anagrammes de manières 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 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 le tri .sort.

Version sans set ni dict

"""
Auteur: Franck CHAMBON
Problème: https://prologin.org/train/2003/semifinal/anagrammes
"""


class Nœud:
    def __init__(self, gauche, élément, droite):
        self.gauche = gauche
        self.élément = élément
        self.droite = droite


class ABR_1:
    """ABR sans doublon"""

    def __init__(self):
        self.racine = None
    
    def est_vide(self):
        return self.racine is None
    
    def ajoute(self, élément):
        "On ajoute sans dupliquer"
        if self.est_vide():
            self.racine = Nœud(ABR_1(), élément, ABR_1())
        elif élément < self.racine.élément:
            self.racine.gauche.ajoute(élément)
        elif élément > self.racine.élément:
            self.racine.droite.ajoute(élément)
        else:
            # en cas d'égalité, on ne fait rien ici
            pass
  
def vers_liste_triée(abr) -> list:
    liste_ordonnée = []
    ajoute = liste_ordonnée.append
    def parcours_infixe(abr):
        if not abr.est_vide():
            parcours_infixe(abr.racine.gauche)
            ajoute(abr.racine.élément)
            parcours_infixe(abr.racine.droite)
    
    parcours_infixe(abr)
    return liste_ordonnée

class ABR_2:
    """ABR qui gère les doublons en comptant les effectifs."""

    def __init__(self):
        self.racine = None
    
    def est_vide(self):
        return self.racine is None
    
    def ajoute(self, signe):
        """On ajoute en comptant les effectifs.
        - `self.racine.élément[0]` est la signature,
        - `self.racine.élément[1]` est l'effectif associé.
        """
        if self.est_vide():
            self.racine = Nœud(ABR_2(), [signe, 1], ABR_2())
        elif signe < self.racine.élément[0]:
            self.racine.gauche.ajoute(signe)
        elif signe > self.racine.élément[0]:
            self.racine.droite.ajoute(signe)
        else:
            # en cas d'égalité, on met à jour l'effectif
            self.racine.élément[1] += 1
    


# cœur du problème

def signature(mot: str) -> str:
    """ Renvoie la signature d'un mot.

    >>> signature('laval')
    'aallv'

    """
    ord_a = ord('a')
    signe = [0 for _ in range(26)]
    for lettre in mot:
        signe[ord(lettre) - ord_a] += 1

    lettres = []
    for i in range(26):
        if signe[i] != 0:
            lettres.append(chr(i + ord_a) * signe[i])
    return "".join(lettres)


def nb_couples_anagrammes(phrase: str) -> int:
    """Renvoie la réponse à notre problème

    >>> début_p = "le chien marche vers sa niche et trouve une limace "
    >>> fin_p = "de chine nue pleine de malice qui lui fait du charme"
    >>> phrase = début_p + fin_p
    >>> nb_couples_anagrammes(phrase)
    6

    """
    mots = phrase.split()

    arbre_mots_uniques = ABR_1() # sans doublon
    for mot in mots:
        arbre_mots_uniques.ajoute(mot)
    
    mots_uniques = vers_liste_triée(arbre_mots_uniques)

    effectif_anagrammes = ABR_2() # gère effectif
    for mot in mots_uniques:
        signe = signature(mot)
        effectif_anagrammes.ajoute(signe)
    
    liste_effectifs = vers_liste_triée(effectif_anagrammes)

    réponse = 0
    for signe, quantité in liste_effectifs:
        réponse += quantité * (quantité - 1) // 2
    return réponse


import doctest
doctest.testmod()

# lecture

nb_caractères = int(input())
phrase = input()


# écriture

print(nb_couples_anagrammes(phrase))