Anagrammes

29-01-2019

Objectifs

  • étude des méthodes split et join sur les chaînes, et sort sur les listes
  • construire et utiliser des dictionnaires
  • comparer l’efficacité de solutions différentes pour un même problème

Quelques méthodes sur les listes et chaînes

Méthode split

  1. Supposons que la variable s a pour valeur la chaîne "la méthode split est parfois bien utile". Quelles sont les réponses fournies par Python pour les expressions suivantes ?
    • s.split(' ')
    • s.split('e')
    • s.split('é')
    • s.split()
    • s.split('')
    • s.split('split')
  2. Déduisez-en une description précise de ce que fait la méthode split.
  3. Cette méthode modifie-t-elle la chaîne à laquelle elle s’applique ?

Méthode join

  1. Supposons que la variable l est définie par l = s.split()s est la chaîne "la méthode split est parfois bien utile". Quelles sont les réponses fournies par Python pour les expressions suivantes ?

    • "".join(l)
    • " ".join(l)
    • ";".join(l)
    • " tralala ".join(l)
    • print ("\n".join(l))
    • "".join(s)
    • "!".join(s)
    • "".join()
    • "".join([])
    • "".join([1,2])
  2. Déduisez-en une description précise de ce que fait la méthode join.

  3. Cette méthode modifie-t-elle la chaîne à laquelle elle s’applique ?

  4. (facultatif) Programmez une fonction join à deux paramètres, le premier une chaîne de caractères, le second une liste de chaînes de caractères, qui renvoie une chaîne de caractères construite en concaténant toutes les chaînes de l en intercalant s sans utiliser la méthode homonyme.

    >>> join('.', ['raymond', 'calbuth', 'ronchin', 'fr'])
    'raymond.calbuth.ronchin.fr'
    

Méthode sort

La méthode sort sur les listes est une méthode qui permet de trier les éléments de la liste sur laquelle elle s’applique. Trier les éléments d’une liste c’est les ranger dans l’ordre. Cette méthode de tri modifie la liste.

>>> l = [3, 1, 4, 1, 5]
>>> l.sort()
>>> l
[1, 1, 3, 4, 5]

On voit sur cet exemple que la liste l a été modifiée après application de la méthode sort : les nombres sont maintenant rangés dans l’ordre numérique croissant.

  1. Appliquez cette méthode sur la liste l = list('timoleon'). Qu’est devenue la liste l ? Même chose avec l = list(s)s = "Je n'ai jamais joué de flûte.".

    À votre avis, si l = list(s) avec s une chaîne de caractères quelconque, quel est l’ordre dans lequel les caractères de l sont rangés après application de la méthode sort ?

  2. Appliquez cette méthode sur la liste l = ['a', 1]. Expliquez la réponse.

Une fonction sort pour les chaînes

Il n’y a pas de méthode sort pour les chaînes de caractères.

  1. Programmez une fonction nommée sort̀ qui renvoie une chaîne de caractères contenant tous les caractères de la chaîne passée en paramètre triés dans l’ordre lexicographique.

    tp_anagrammes.sort(s)
    Paramètres:s – (str) une chaîne de caractères
    Renvoie:(str) une chaîne de caractères contenant les caractères de s triés dans l’ordre croissant.
    CU:aucune
    Exemple:
    >>> sort('timoleon')
    'eilmnoot'
    

    Pour cela, vous pourrez utiliser avec profit la fonction de conversion list, la méthode sort des listes et la méthode join des chaînes.

Anagrammes

Selon le dictionnaire « Le Petit Robert », le mot anagramme a pour définition : mot obtenu par transposition des lettres d’un autre mot.

Une anagramme est donc un mot constitué des mêmes lettres qu’un autre en respectant leurs nombres d’occurrences. Par exemple orange est une anagramme du mot organe, ainsi que onagre.

Dans cette partie nous étendons la notion d’anagrammes à toute chaîne de caractères : deux chaînes de caractères sont dites anagrammatiques si elles contiennent les mêmes caractères en mêmes nombres. En particulier toute chaîne de caractère est une anagramme d’elle-même.

Vous allez écrire plusieurs versions d’un prédicat nommé sont_anagrammes qui prend deux chaînes de caractères et renvoie le booléen True si ces deux chaînes sont anagrammatiques, et le booléen False dans le cas contraire.

tp_anagrammes.sont_anagrammes(s1, s2)
Paramètres:s2 (s1,) – (str) deux chaînes de caractères
Renvoie:(bool) - True si s1 et s2 sont anagrammatiques - False sinon
CU:aucune
Exemples:
>>> sont_anagrammes('orange', 'organe')
True
>>> sont_anagrammes('orange','Organe')
True

Mise à part la dernière, les versions du prédicat sont_anagrammes que vous réaliserez feront la distinction des lettres

  • d’une part, selon leur casse (majuscule/minuscule) : Orange et oRaNgE ne sont pas anagrammes,
  • d’autre part, selon leur accentuation : orangé et orange ne sont pas anagrammes.
  1. Réalisez une première version du prédicat en utilisant la fonction sort.
  2. Réalisez une deuxième version du prédicat en construisant un dictionnaire du nombre d’occurrences des caractères pour chacune des deux chaînes passées en paramètre.
  3. Réalisez enfin une troisième version en parcourant les caractères de l’une des deux chaînes, et en comparant son nombre d’occurrences dans cette chaîne (méthode count) avec le nombre d’occurrences dans l’autre chaîne.

Casse et accentuation

Dans de nombreuses situations, comme par exemple dans les jeux de Scrabble, ou du mot le plus long, il n’y a pas lieu de se préoccuper de la casse des lettres ou bien de leur accentuation. Dans ce cas, les chaînes orangé et ORGANE sont anagrammatiques.

Dans ce travail, nous ne nous intéresserons qu’aux lettres accentuées de la langue française.

  1. Définissez un dictionnaire nommé EQUIV_NON_ACCENTUE qui associe à chacune des lettres accentuées de la langue française son équivalent non accentué.

  2. Définissez une fonction nommée bas_casse_sans_accent qui renvoie une chaîne de caractères identiques à celle passée en paramètre sauf pour les lettres majuscules et les lettres accentuées qui sont converties en leur équivalent minuscule non accentué. Vous pourrez utiliser le dictionnaire défini ci-dessus, ainsi que la méthode lower des chaînes de caractères.

    >>> bas_casse_sans_accent('Orangé')
    'orange'
    
  3. En utilisant cette fonction, réalisez une dernière version du prédicat sont_anagrammes qui ne différencie pas les lettres selon leur casse ou leur accentuation.

    >>> sont_anagrammes('Orangé', 'organE')
    True
    

Recherche d’anagrammes

Dans cette partie, le but est de construire la liste des anagrammes d’un mot donné. Les mots que l’on considère sont des mots existant dans un lexique donné.

Le lexique

Le lexique dans lequel vous puiserez les mots autorisés est donné sous forme d’une liste définie dans un module nommé lexique.

  1. Commencez par le récupérer en téléchargeant l’archive lexique.zip.

  2. Décompressez cette archive dans le dossier dans lequel vous travaillez. Vous devez obtenir les deux fichiers

    • lexique.txt qui contient la liste des mots du lexique. C’est un fichier texte ordinaire, il ne contient aucun code en Python. [1]
    • lexique.py qui contient la définition du lexique utilisable dans un programme en Python.

    Vous pouvez étudier le contenu de ces fichiers si vous le souhaitez, mais ce n’est pas nécessaire pour le travail que vous aurez à faire. En aucun cas vous ne pouvez modifier le fichier lexique.py pour ce TP.

    En revanche, pour pouvoir utiliser ce module vous aurez à utiliser la commande

    from lexique import LEXIQUE
    

    Ce module définit essentiellement une variable nommée LEXIQUE qui contient la liste des mots contenus dans le fichier lexique.txt.

  3. Combien de mots contient ce lexique ?

  4. Ce lexique contient-il des doublons ?

Anagrammes d’un mot : première méthode

L’objectif de ce paragraphe, et du suivant, est la réalisation d’une fonction nommée anagrammes qui renvoie la liste des anagrammes d’un mot passé en paramètre, ces anagrammes appartenant au lexique

tp_anagrammes.anagrammes(mot)
Paramètres:mot – (str) un mot dont on veut les anagrammes.
Renvoie:(list) la liste des mots figurant dans le LEXIQUE qui sont des anagrammes de mot.
CU:aucune
Exemple:
>>> anagrammes('orange')
['onagre', 'orange', 'orangé', 'organe', 'rongea']
>>> anagrammes('info')
['foin']
>>> anagrammes('Calbuth')
[]
  1. Réalisez une première version de cette fonction qui effectue la recherche des anagrammes du mot en parcourant l’intégralité du lexique.
  2. Recherchez la liste des anagrammes du mot chien.

Anagrammes d’un mot : seconde méthode

Une autre méthode tout à fait différente pour réaliser la fonction anagrammes consiste à établir une fois pour toute un dictionnaire dont les valeurs sont toutes les listes d’anagrammes que l’on peut faire à partir du lexique.

  1. Expliquez pourquoi il n’est pas raisonnable de prendre les mots du lexique pour clés.

  2. Les clés du dictionnaire seront les versions triées des lettres du mot après transformation du mot en bas de casse sans accent.

    Réalisez donc une fonction nommée cle qui calcule la clé que doit avoir un mot donné dans le dictionnaire.

    Par exemple ::
    >>> cle('Orangé')
    'aegnor'
    
  3. Construisez le dictionnaire des anagrammes, dont chaque association a pour clé la clé d’un mot du lexique, et pour valeur la liste des anagrammes. Vous nommerez ANAGRAMMES ce dictionnaire. À titre de vérification, avec le lexique fourni vous devrez obtenir

    >>> len(ANAGRAMMES)
    118625
    
  4. Réalisez enfin une deuxième version de la fonction anagrammes qui utilise ce dictionnaire.

  5. Recherchez la liste des anagrammes du mot chien.

Comparaison des deux méthodes

Nous voilà avec deux méthodes pour rechercher la liste des anagrammes d’un mot. Laquelle est la plus rapide ?

  1. Pour répondre à cette question, écrivez une instruction qui imprime les longueurs des listes d’anagrammes des 30 premiers mots du lexique avec chacune de vos deux fonctions.

    Que constatez-vous ?

Phrases d’anagrammes

Partie facultative.

Dans cette partie, une phrase est constituée de mots séparés par de simples espaces.

  1. Réalisez une fonction nommée anagrammes_phrase qui prend une phrase et renvoie la liste des phrases obtenues en remplaçant chacun des mots par leurs anagrammes.

    >>> anagrammes_phrase('Mange ton orange')
    ['mange ont onagre', 'mange ont orange', 'mange ont orangé', 'mange ont organe', 'mange ont rongea', 'mange ton onagre', 'mange ton orange', 'mange ton orangé', 'mange ton organe', 'mange ton rongea', 'mangé ont onagre', 'mangé ont orange', 'mangé ont orangé', 'mangé ont organe', 'mangé ont rongea', 'mangé ton onagre', 'mangé ton orange', 'mangé ton orangé', 'mangé ton organe', 'mangé ton rongea']
    

Notes

[1]ce fichier est le dictionnaire utilisé dans les distributions Debian de Linux.