Anagramme

Définition

Un mot est une anagramme d'un autre mot s'ils ont exactement les mêmes lettres.

Exemples:

• aimer et marie
• marion et manoir
• casser et ressac

Par contre 'miam' et 'iam' ne sont pas des anagrammes: les lettres sont les mêmes mais pas avec le même effectif.

Exercice 1

Gus doit écrire le code d'une fonction prenant deux mots en paramètre et renvoyant True si ces deux mots sont anagrammes l'un de l'autre et False sinon.

Il propose le code suivant:

def sont_anagrammes(mot1,mot2):
    """
    mot1 -- chaîne de caractères
    mot2 -- chaîne de caractères

    renvoie True si mot1 et mot2 sont anagrammes,
    False sinon
    """
    for lettre in mot1:
        if lettre not in mot2:
            return False
    return True

Les tests suivants semblent indiquer une fonction correcte:

>>> sont_anagrammes('aimer','marie')
True
>>> sont_anagrammes('aha','ubu')
False

Montrer que ce code ne convient pas en explicitant un test adéquat. Expliquez le problème.

Un test

>>> sont_anagrammes('aimer','marier')
True

Le test renvoie True alors que 'marier' contient une lettre r de trop.

Explication

Le code vérifie que chaque lettre du premier mot est présente dans le second mot... mais ne vérifie pas si elle est présente avec un plus grand nombre d'occurrences.

Exercice 2

Pour corriger le problème souligné à l'exercice précédent, Gus propose le code suivant:

def compte(mot, lettre):
    """
    mot -- chaîne de caractères
    lettre -- caractère

    renvoie le nombre d'occurrences de lettre dans mot
    """
    compteur = 0
    for carac in mot:
        if carac == lettre:
            compteur += 1
    return compteur


def sont_anagrammes(mot1,mot2):
    """
    mot1 -- chaîne de caractères
    mot2 -- chaîne de caractères

    renvoie True si mot1 et mot2 sont anagrammes,
    False sinon
    """
    for lettre in mot1:
        if compte(mot1, lettre) != compte(mot2, lettre):
            return False
    return True

Les tests suivants semblent indiquer un code correct:

>>> sont_anagrammes('aimer','marie')
True
>>> sont_anagrammes('aimer','marier')
False
>>> sont_anagrammes('uhu','aba')
False

Montrer, en explicitant un test adéquat, que le code n'est pas correct.

Un test

>>> sont_anagrammes('aimer','marie-b')
True

Le code ne vérifie pas si le mot2 ne contient pas d'autres lettres que le mot1.

Exercice 3

Proposer une correction du code précédent.

Un code

def compte(mot, lettre):
    """
    mot -- chaîne de caractères
    lettre -- caractère

    renvoie le nombre d'occurrences de lettre dans mot
    """
    compteur = 0
    for carac in mot:
        if carac == lettre:
            compteur += 1
    return compteur


def sont_anagrammes(mot1,mot2):
    """
    mot1 -- chaîne de caractères
    mot2 -- chaîne de caractères

    renvoie True si mot1 et mot2 sont anagrammes,
    False sinon
    """
    for lettre in mot1:
        if compte(mot1, lettre) != compte(mot2, lettre):
            return False
    for lettre in mot2:
        if compte(mot1, lettre) != compte(mot2, lettre):
            return False
    return True

Exercice 4

Dans la solution précédente, le code de la fonction sont_anagrammes présente deux blocs de structures identiques (le bloc for lettre in mot1: ... et le bloc for lettre in mot2: ...).

Ce type de répétition dans le code est typiquement ce que l'on vous demandera tout au long de l'année d'éviter: dès qu'un code est répété, créez une fonction intermédiaire évitant la répétition.

Réécrivez le programme du corrigé de l'exercice précédent en éliminant cette répétition.

Un code possible

La fonction est_composable ci-dessous ne reprend pas tout à fait le code répété: on a remplacé l'égalité par une inégalité. A vous de comprendre pourquoi cela suffit.

def compte(mot, lettre):
    """
    mot -- chaîne de caractères
    lettre -- caractère

    renvoie le nombre d'occurrences de lettre dans mot
    """
    compteur = 0
    for carac in mot:
        if carac == lettre:
            compteur += 1
    return compteur


def est_composable(mot, jeu):
    """
    mot -- chaîne de caractères
    jeu -- chaîne de caractères

    jeu est un ensemble de lettres (que l'on peut voir comme 
    le jeu de lettres dont on dispose au scrabble au moment où l'on doit jouer)

    renvoie True si on peut écrire mot avec les lettres disponibles dans jeu, 
    et renvoie False sinon.
    >>> est_composable('aha', 'ahbc')
    False
    >>> est_composable('aha', 'ahbac')
    True
    >>> est_composable('aha', 'ahbaa')
    True
    """
    for lettre in mot:
        if compte(mot, lettre) > compte(jeu, lettre):
            return False
    return True



def sont_anagrammes(mot1,mot2):
    """
    mot1 -- chaîne de caractères
    mot2 -- chaîne de caractères

    renvoie True si mot1 et mot2 sont anagrammes,
    False sinon
    """
    return est_composable(mot1, mot2) and est_composable(mot2, mot1)