Solution du problème Anagram¶

Vous trouverez ici la solution pour l'exercice suivant:

Exercice de base¶

Il nous faut voir si deux texte sont composés des même lettre. La première idée serait de faire un set a partir de chacun des textes et de vérifier si ils sont égaux:

def is_anagram(text1, text2):
    return set(text1) == set(text2)

Alors, c'est bien mais ca ne va marcher que pour certaines anagrammes: si on a des lettre en double, elles ne compteront que pour une, et ainsi "toto" et "to" sont déclarés comme anagrammes alors que les deux textes n'en sont pas.

Une autre possibilité, mettre les lettres dans l'ordre, et comparer. Si deux textes sont des anagrammes, alors ils seront identiques en les triants par ordre alphabetique (et le nombre de lettre sera pris en compte).

def is_anagram(text1, text2):
    return sorted(text1) == sorted(text2)

Il va donc nous falloir compter le nombre d'occurence pour chacune des lettres dans chacun des textes et vérifier l'égalité. Pour cela on peut passer par un dictionaire avec comme clef la lettre, et comme valeur, le nombre d'occurence. Faisons une méthode count_letters afin de ... compter les lettres.

def count_letters(text):
    letters = dict()
    for c in text:
        letters.setdefault(c, 0)
        letters[c] += 1
    return letters

On peut voir l'utilisation de dict.setdefault qui permet d'initialiser une valeur d'un dictionaire si elle n'existe pas encore. Donc si c n'est pas encore dans le dictionaire, on l'initialise à 0.

Une autre possibilité serait d'utiliser la methode dict.get pour récuperer la valeur associée a un charactère, et a defaut, une valeur par defaut:

def count_letters(text):
    letters = dict()
    for c in text:
        letters[c] = letters.get(c, 0) + 1
    return letters

Ensuite il ne nous reste qu'a utiliser cette fonction pour compter les lettres:

def is_anagram(text1, text2):
    return count_letters(text1) == count_letters(text2)

Comme spécifié dans l'exercice de base, il ne faut pas oublier de gérer les majuscules qui peuvent être dans les textes d'entrée. Pour cela, rien de plus simple, il suffit de convertir le texte en minuscules:

def count_letters(text):
    letters = dict()
    for c in text.lower():
        letters[c] = letters.get(c, 0) + 1
    return letters


def is_anagram(text1, text2):
    return count_letters(text1) == count_letters(text2)

Et voila pour l'exercice de base.

Mais j'avais demandé plusieurs solution et nous en avons déjà 2: l'ordre alphabétique et le comptage de lettres en 2 exemplaires. Je vais vous en donner deux autres.

La fonction count_letters est "complexe" car nous cherchons toujours si une valeure est déjà enregistrée. Si nous pouvions nous débarasser de ce teste, cela serait bien plus simple. Pour cela, nous allons utiliser un defaultdict dont le but est justement de retourner une valeur par default si la valeur n'existe pas déjà.

from collections import defaultdict
def count_letters(text):
    letters = defaultdict(int)
    for c in text.lower():
        letters[c] += 1
    return letters

La dernière solution va utiliser un objet que nous avons déjà vu: Counter dont le but est de compter les occurences dans un iterable. Et cela tombe bien, un texte est un iterable, et on veut compter les occurences des lettres.

Du coup, count_letters peut s'ecrire:

from collections import Counter

def count_letters(text):
    return Counter(letters.lower())


def is_anagram(text1, text2):
    return count_letters(text1) == count_letters(text2)

Bonus 1¶

Il va falloir gérer les anagrammes sur plusieurs mots. Pour cela il suffit d'ignorer les espaces.

from collections import Counter

def count_letters(text):
    return Counter(letters.lower().replace(" ", ""))


def is_anagram(text1, text2):
    return count_letters(text1) == count_letters(text2)

Et voila, vite fait bien fait...

Bonus 2¶

Il nous faut ignorer la ponctuation. Si on veut procéder comme pour les espaces, il va nous falloir faire un très grand nombre d'appels à replace. Il serait plus judicieux de chercher les charactères qui sont des lettres. Et cela tombe bien, en python, un texte a une methode pour cela: isalpha. Cette methode retourne True si le texte n'est composé que de lettres. Ce qui ici est fort utile:

from collections import defaultdict
def count_letters(text):
    letters = defaultdict(int)
    for c in text.lower():
        if c.isalpha():
            letters[c] += 1
    return letters

def is_anagram(text1, text2):
    return count_letters(text1) == count_letters(text2)

Une autre possibilité: enlever tous les charactères qui ne sont pas des lettres. Afin de faire cela, il va falloir utiliser les expressions rationnelles:

import re
from collections import Counter

def count_letters(text):
    return Counter(re.sub("[^a-z]", "", letters.lower()))


def is_anagram(text1, text2):
    return count_letters(text1) == count_letters(text2)

Une petite note comme cela en passant: en Python, une fonction peut être définie dans une autre fonction. Cela permet de "cacher" cette fonction au reste du code. Si on veut factorizer certaines lignes de code, mais que le domaine de définition doit rester local, alors on peut définir une fonction dans une fonction. C'est le cas ici, count_letters peut être défini localement:

import re
from collections import Counter

def is_anagram(text1, text2):
    def count_letters(text):
        return Counter(re.sub("[^a-z]", "", letters.lower()))

    return count_letters(text1) == count_letters(text2)

Bonus 3¶

Là cela va être très simple d'un point de vu code, mais plus complexe à comprendre. Il faut faire en sorte qu'une lettre puisse correspondre à une autre. Plus précisément, faire en sorte qu'un à puisse compter pour un a sans accent.

Pour reussir ce tour de force, nous allons utiliser le module unicodedata afin de convertir les lettres avec accent en lettre + marquer d'accent. En gros, schématiquement, on peut ecrire un à en une seule lettre unicode, ou bien en 2: a et ajoute un accent à la lettre précédente.

Comme notre algo par la suite retirera tout le charactères non alphabetiques, il ne restera que le a, et le tour sera joué.

Pour faire cette décomposition, on va utiliser la methode unicodedata.normalize(). Il faudra lui donner comme premier parametre "NFD" afin d'optenir le résultat souhaité.

from unicodedata import normalize
from collections import Counter

def is_anagram(text1, text2):
    def count_letters(text):
        return Counter(
            re.sub(
                "[^a-z]",
                "",
                normalize('NFD', letters.lower())
            )
        )

    return count_letters(text1) == count_letters(text2)

Et voila, tout est fait, à la prochaine fois.