Anagrammes et Python

Comment vérifier que deux chaînes de caractères sont des anagrammes en Python ? Plusieurs logiques peuvent être envisagées. Regardons cela.

Qu’est-ce qu’une anagramme ?

ben oui, avant de parler d’anagrammes, il faut savoir ce que c’est non ?

Une anagramme (oui, c’est féminin) d’une chaîne de caractères est une chaîne de caractères formée des mêmes caractères mis dans un ordre différent.

Ainsi, “ABC” et “BAC” sont deux anagrammes.

Nous allons supposer par la suite que a et b sont deux chaînes de caractères de même longueur (pour les calculs de complexité).

Anagrammes et Python : première méthode

La méthode la plus simple pour voir si deux chaînes de caractères sont anagrammes est la suivante:

def anagramme(a,b):
    if sorted(a) == sorted(b):
        return True
    else:
        return False

La complexité est en \(\mathcal{O}(n\ln n)\) en moyenne, où n est le nombre de caractères d’une chaîne. En effet, l’algorithme de tri utilisé par Python est timsort.

Une deuxième approche : anagrammes et Python

Cette méthode est quasi-analogue à la précédente, si ce n’est qu’elle fait appel au module collections.

from collections import Counter

def anagramme(a,b):
    if Counter(a) == Counter(b):
        return True
    else:
        return False

Counter(a) est un objet, défini par la classe Counter, qui se comporte comme un dictionnaire. C’est d’ailleurs une sous-classe de dict.

La complexité de cette solution est alors en \(\mathcal{O}(n)\).

Une troisième approche : anagrammes et Python

S’inspirant de la méthode précédente, on peut construire directement un dictionnaire à partir de la chaîne de caractères:

def anagramme(a,b):
    dict_a , dict_b = dict() , dict()
    for i in a:
        dict_a[i] = 1 if i not in dict_a else dict_a[i]+1
    for i in b:
        dict_b[i] = 1 if i not in dict_b else dict_b[i]+1
    
    if dict_a == dict_b:
        return True
    else:
        return False

On voit bien ici que la complexité est en \(\mathcal{O}(n)\).

Conclusion

Si on cherche a avoir une complexité minimale, ainsi qu’une syntaxe minimale, il vaut mieux utiliser le module collections et la classe Counter.

Cet article est en marge des ressources Python pour le lycée, disponibles sur cette page.

Construire toutes les anagrammes

Concernant la génération de toutes les anagrammes d’un mot, c’est une autre affaire, bien plus complexe!

Il existe de nombreuses façons d’implémenter la génération d’anagrammes, la plupart reposant sur le principe de récursivité. Mais attention aux solutions trop gourmandes du point de vue ressources… car il est très facile de saturer la RAM avec ce genre de choses!

Dans le programme suivant, de seulement 8 lignes, je choisis d’utiliser le mot-clé yield, très peu utilisé au lycée (voire pas du tout car très compliqué à cerner à ce niveau) car il permet la manipulation de nombreuses données.

def anagrammes(mot):
    if len(mot) == 1:
        yield mot
    else :
        for z in set(mot): # set(mot) permet de créer un ensemble de lettres DISTINCTES
            i = mot.index(z)
            for sm in anagrammes( mot[0:i] + mot[i+1:] ):
                yield z + sm

>>> for m in anagrammes("MOTO"): print(m)
TOOM
TOMO
TMOO
OTOM
OTMO
OMTO
OMOT
OOTM
OOMT
MTOO
MOTO
MOOT

L’idée ici est de construire une fonction récursive anagrammes(mot) qui consiste à retourner le mot lui-même s’il n’est constitué que d’une seule lettre, et sinon, de parcourir ce mot lettre à lettre et de former une anagramme commençant par cette lettre et formée ensuite de toutes les anagrammes du mot restant une fois que l’on lui a ôté cette lettre (d’où la récursivité).

Bien entendu, la liste complète peut s’avérer très longue et la plupart des anagrammes peuvent être insensés. C’est la raison pour laquelle est il serait intéressant d’ajouter une sorte de filtre. On aurait ainsi uniquement les mots qui existent.

Je vous propose alors le script suivant:

from unidecode import unidecode

def anagrammes(mot):
    if len(mot) == 1:
        yield mot
    else :
        for z in set(mot): # set(mot) permet de créer un ensemble de lettres DISTINCTES
            i = mot.index(z)
            for sm in anagrammes( mot[0:i] + mot[i+1:] ):
                yield z + sm

def anag(mot):
    mot = mot.upper()
    M = []
    
    # on construit une liste des mots de même longueur que 'mot'
    
    with open('mots.txt' , 'r' , encoding='utf-8') as w:
        for l in w:
            if len(l[:-1]) == len(mot) and unidecode(l[:-1]) not in M:
                M.append(unidecode(l[:-1]))
    
    L = [ word for word in M if word in anagrammes(mot) ]
        
    return L

On aurait ainsi, par exemple:

>>> anag('NICHE')
['CHIEN', 'CHINE', 'NICHE']

Vous avez sans doute remarqué la présence du fichier externe mots.txt qui contient tous les mots de la langue (on peut trouver ce genre de fichiers en faisant une recherche sur le net, comme par exemple ici).

Le problème de ce script est tout de même sa complexité. En effet, pour afficher les anagrammes de “python”, il faut un peu plus que 18 secondes ! Autant dire qu’il n’est pas du tout performant…

Je vais donc légèrement modifier le script précédent afin que sa complexité soit bien moindre:

from unidecode import unidecode
from itertools import permutations 

def anagrammes(mot):
    mot = mot.upper()
    M = []
    A = [''.join(list(i)) for i in permutations(mot) ]
    
    # on construit une liste des mots de même longueur que 'mot'
    
    with open('mots.txt' , 'r' , encoding='utf-8') as w:
        for l in w:
            if len(l[:-1]) == len(mot) and unidecode(l[:-1]) not in M:
                M.append(unidecode(l[:-1]))
    
    L = [ word for word in M if word in A]
        
    return L

C’est bien meilleur: 1,61 seconde pour:

>>> anagrammes('python')
['PYTHON', 'TYPHON']

Près de 11 fois plus rapide! Ouf!