Partage
  • Partager sur Facebook
  • Partager sur Twitter

[Programme] Besoin aide ou développeur

Création d'un programme pour créer des histoires de CP

Sujet résolu
    5 avril 2020 à 17:19:33

    Bonjour à tous!

    Je suis professeure des écoles d'une classe de CP. J'aurais besoin d'un petit programme tout simple pour m'aider à écrire des textes à mes élèves, en respectant leur niveau de lecture. Je ne sais pas du tout comment le faire ni avec quel programme (Excel, Access... autre?). J'aurais donc besoin de l'aide de quelqu'un. 

    En savoir plus sur le projet

    Genèse

    C'est tout simple: en début d'année, mes élèves ne connaissent pas toutes les lettres de l'alphabet. Or, j'ai besoin de leur écrire des petites histoires, avec des mots comportant des lettres déjà étudiées. J'ai fait des recherches sur Internet pour trouver un outil me permettant de recenser tous les mots avec les lettres étudiées, mais en vain. Le meilleur site que j'ai trouvé est dcode.fr, section "recherche de mots". Mais ce site ne correspond pas totalement à ma requête, les résultats sont notamment limités à 1000 mots seulement.

    Généralités et avancement

    J'aurais donc besoin d'un petit programme tout simple, me permettant d'obtenir, à partir d'une base de données, une liste de mots:

    - Contenant: [une ou plusieurs des lettres étudiées] - Exemple: je recherche des mots contenant une ou plusieurs des lettres suivantes: a, e, i, o, u, é, è, y, m, l, r

    - Finissant par: [les lettres étudiées + des lettres muettes] -  Exemple:  je recherche des mots contenant une ou plusieurs des lettres suivantes: a, e, i, o, u, é, è, y, m, l, r + pouvant se terminer par un s, un t, ou un z . Cela me permettrait d'avoir les mots suivants: rat, riz etc... lisibles par mes élèves si je grise la dernière lettre muette.

    Objectifs

    Comme dit plus haut, ce petit programme me permettrait de créer des histoires au niveau de mes élèves et les motiver à lire.

    Par l'intermédiaire de ce forum, je recherche soit des personnes qui pourraient m'indiquer comment créer ce programme (Excel, Access ou autre programme je ne sais pas? Vers quels tutos ou cours me diriger?), soit des personnes qui pourraient me le créer, contre rémunération. 

    Je vous remercie d'avance pour votre aide!

    Laurie

    • Partager sur Facebook
    • Partager sur Twitter
      5 avril 2020 à 19:20:38

      Salut,

      je suis en train de faire un petit test avec ce que tu veux, ça serait une simple page html que tu glisses dans ton navigateur (même sans connexion donc). Comment obtiens-tu les mots? Tu as déjà une base de données?

      • Partager sur Facebook
      • Partager sur Twitter
        5 avril 2020 à 19:37:05

        Merci c'est super gentil! J'ai trouvé une base de données Excel sur le site Lexique.org. Il y a 140 000 mots, c'est pas mal:

        http://www.lexique.org/ > Télécharger Lexique 3.83 

        Est-ce que ça correspond à ce que tu souhaites? 

        Tu me diras combien je te dois!

        -
        Edité par Laurie14 5 avril 2020 à 19:38:26

        • Partager sur Facebook
        • Partager sur Twitter
          5 avril 2020 à 20:10:23

          Alors en fait j'avais fait une page avec des expressions régulières, mais avec Excel je ne sais pas faire.

          Mais! J'ai regardé sur le site que tu as donné, et ils proposent eux-mêmes la même fonctionnalité, regarde ici : http://www.lexique.org/?page_id=101 

          Donc si tu vas sur leur page avec tous les mots : http://www.lexique.org/shiny/openlexicon/

          Dans la première case, sous le mot "Word", tu peux faire une recherche. Si tu vas sur la page des "expressions régulières",  http://www.lexique.org/?page_id=101 , ils te donnent des exemples, comme : "ion$ : mots se terminant par “ion” ($=fin de mot)"

          Donc si tu copies colles "ion$" dans la case sous "Word", tu auras tous les mots qui se terminent par "ion" (le $ veut dire "fin du mot")

          Autre exemple, si tu as besoin d'un mot qui contient "o" et "é", alors tu les mets comme ça : [o][é] : coéquipière.

          Si tu mets "oé", il va chercher les mots avec au moins "o" ou au moins "é", donc "réglé" ou "boule" sera sélectionné, ou coéquipière.

          Il faut s'entraîner un peu mais si tu as un soucis, tu peux demander ici :D

          Autre exemple : "riz" ou "riez" : tu mettrais : ^r.*z$ 

          C'est-à-dire : ^r      .*     z$

          On "commence" par r , en utilisant le chapeau ^

          on veut n'importe quelle lettre (le point . ) répété 0 ou plusieurs fois (l'étoile *)

          et ce mot doit se terminer par "z" : le dollar z$

          -
          Edité par Arthur222 5 avril 2020 à 20:16:39

          • Partager sur Facebook
          • Partager sur Twitter
            5 avril 2020 à 20:51:34

            Merci beaucoup d'avoir pris le temps de regarder tout ça.

            J'avais vu ces fonctionnalités mais je n'avais rien compris, tes explications sont beaucoup plus claires.

            Par contre quand je mets "oé" sous Word, le site ne me propose que des mots avec les deux lettres ensemble genre "cOÉquipière", "pOÉtique"... Je me suis trompée dans la formulation?

            Par ailleurs, quelle serait la formule pour trouver des mots avec certaines lettres + se terminant par certaines lettres muettes?

            Par exemple, je veux trouver tous les mots avec "a", "e", "i", "o", "u", "m", "r", "s", "l" se terminant soit par ces lettres soit par un "t" ou un "x"?

            • Partager sur Facebook
            • Partager sur Twitter
              5 avril 2020 à 21:12:39

              Salut,

              J'ai trouvé un github qui sépare la nature des mots, je ne sais pas combien il y a de mots au total. Ainsi qu'un autre site qui recense 208K mots (+ 50 %).

              Avec la suite Office, juste en passant, c'est dommage que l'EN n'insiste pas davantage sur les logiciels libres*, tu as le langage VBA qui possède un module sur les expressions régulières dont j'ai découvert le nom sur ce lien. Fais attention à la date du message qui a environ 4 ans, la version a sans doute évolué, voire changé de nom.

              Enfin, sur ce site, 2 chapitres PHP sont consacrés aux expressions régulières.

              * Je souhaiterais tellement que nos impôts envers l'EN soient utilisés pour des voyages bien plus que pour des logiciels dont les alternatives libres et gratuites existent. J'ai connu les restrictions budgétaires il y a une vingtaine d'années où ma classe n'a pas pu aller en classe verte ET en classe blanche, et je n'étais qu'en primaire.

              • Partager sur Facebook
              • Partager sur Twitter
                5 avril 2020 à 22:31:46

                Laurie14 a écrit:

                Par contre quand je mets "oé" sous Word, le site ne me propose que des mots avec les deux lettres ensemble genre "cOÉquipière", "pOÉtique"... Je me suis trompée dans la formulation?

                Par ailleurs, quelle serait la formule pour trouver des mots avec certaines lettres + se terminant par certaines lettres muettes?

                Par exemple, je veux trouver tous les mots avec "a", "e", "i", "o", "u", "m", "r", "s", "l" se terminant soit par ces lettres soit par un "t" ou un "x"?

                Pour avoir "obligatoirement" 2 lettres spécifiques, je ne sais pas, mais tu peux faire 2 recherches comme ça :

                o+.*a+  

                a+.*o+

                Le "+" est différent de "*", le + c'est au moins 1 ou plusieurs, l'étoile c'est 0 ou plusieurs.

                Pour ton exemple qui finit par x ou t, tu peux faire comme ça :

                (a|o).*[xt]$

                donc (a|o) c'est pareil que [ao] ça veut dire "a ou o". Tu peux mettre ce que tu veux : (a|o|u|i|y) ou [aouiy]

                .* veut dire : "suivre par n'importe quelle lettre, 0 ou plusieurs fois"

                et [xt]$ veut dire : "le mot se terminera par x ou t"

                Tu auras "évoquent", "abdominaux", etc. etc. il y a beaucoup de mot qui se finissent par "t", mais il y a bien ceux qui se finissent par "x" dans la liste.

                -
                Edité par Arthur222 6 avril 2020 à 2:33:52

                • Partager sur Facebook
                • Partager sur Twitter
                  6 avril 2020 à 0:00:47

                  Bonjour ! Si tu utilises Linux, il y a un dictionnaire de 139719 mots français (avec les accents, les différentes conjugaison et tout) dans /usr/share/dict : le fichier "french". Je ne sais pas si on peut le trouver sur Internet (par exemple sur une page consacrée à Linux) ?

                  Dans ce fichier, chaque mot occupe une ligne. Il doit donc être facile d'écrire un petit script Python pour générer une liste de mots selon divers critères. Sinon, effectivement on doit pouvoir faire des choses avec les expressions régulières (mais là je ne connais pas). Mais si j'ai bien compris tu ne programmes pas...

                  Ce qui serait faisable, c'est que quelqu'un écrive un script Python pour générer la liste des mots extraits de ce fichier contenant certaines lettres et finissant par certaines autres lettres, et tu n'aurais qu'à réutiliser ce script en changeant à ta guise les liste de lettres en question.

                  Justement, j'essaie de réviser le langage Python, que je n'ai pas pratiqué depuis deux ans. Du coup, ça me paraît un bon petit exercice de débutant. Tu aurais envoyé ton message hier, j'aurais pu m'amuser à faire ça aujourd'hui... Mais j'essaierai cette semaine : même si ça ne te sert pas, c'est une exercice concret, donc intéressant.

                  -
                  Edité par robun 6 avril 2020 à 0:04:00

                  • Partager sur Facebook
                  • Partager sur Twitter
                    Staff 6 avril 2020 à 1:56:43

                    Bonjour,

                    Déplacement vers un forum plus approprié

                    Le sujet est déplacé de la section Discussions générales vers la section Recrutements pour vos projets

                    • Partager sur Facebook
                    • Partager sur Twitter
                      6 avril 2020 à 11:35:09

                      Merci infiniment Arthur22 et LeCobriste128!

                      Grâce à vos explications et à vos liens, j'ai réussi à trouver le code qui me permet d'obtenir exactement ce que je veux sur le site lexique.org.

                      Vous m'avez épargné beaucoup d'heures de recherche et de prise de tête! C'est vraiment super sympa de votre part! Si vous avez des futurs petits élèves de CP dans votre famille, je pourrai vous envoyer mes petites histoires illustrées quand elles seront terminées :-) 

                      Robun, tu fais comme tu veux. Si tu veux t'entrainer sur Python, alors c'est avec plaisir que je testerai ton programme! Je pense qu'il pourra bien me servir, ne serait-ce que si un jour le site lexique.org dysfonctionne...

                      Je vous souhaite une excellente journée à tous! 

                      • Partager sur Facebook
                      • Partager sur Twitter
                        6 avril 2020 à 13:11:26

                        Oui, je vais faire ce programme à titre d'exercice. Mais je pense que je vais en faire un peu plus que ce qui t'es nécessaire (en gros il y aura de la recherche de lettres (qui sont dans le mot ou qui n'y sont pas) mais aussi de motifs (en début de mot, en fin de mot, n'importe où)). En fait, je me rends compte que c'est un très bon sujet d'exercice (entraînement sur les boucles, le « slicing », la manipulation de chaînes de caractères...)

                        --------------------------------------------------------------------------------------

                        Je viens de commencer ce soir. Je te montre le début au cas où tu aurais des commentaires.

                        Le programme demande trois choses :

                        1) la liste des lettres qui serviront pour la recherche ;

                        2) le motif qui servira pour la recherche ;

                        3) le nom du fichier où seront écrits les mots trouvés.

                        Pour le 1) :

                        Lettres à sélectionner                     ==> cir
                        
                        Recherche des mots : 
                            1. contenant au moins une des lettres
                            2. contenant au moins une de chacune des lettres
                            3. contenant uniquement au moins une des lettres
                            4. contenant uniquement chacune des lettres
                            5. anagrammes
                            0. ne contenant aucune des lettres
                                                                   ==> 3
                        

                        Les lettres sélectionnées doivent être écrites à la suite, sans espace, sans virgule (qui seraient considérées comme des lettres). Là j'ai choisi trois lettes : C, I et R (le programme convertit tout en minuscules, là je les écris en majuscules par flemme de mettre des guillemets).

                        Option 1 : tous les mots contenant au moins C, I ou R. Exemple : écran.

                        Option 2 : tous les mots contenant au moins un C, au moins un I et moins un R. Exemple : clavier (mais pas écran : il manque le I).

                        Option 3 : mots ne contenant que des C, des I ou des R. Exemple : ici.

                        Option 4 : mots ne contenant que des C, des I et des R (il faut les trois, et que les trois). Exemple : cric

                        Option 5 : anagrammes. Là je ne vois que : cri.

                        Option 0 : mots ne contenant pas de C, ni de I, ni de R. Exemple : banane.

                        Il me semble que ça couvre bien tous les cas de figure. C'est très simple et même amusant à programmer en Python (j'ai déjà écrit cette partie, j'ai juste un petit problème de syntaxe dû mes lacunes). Mon langage de prédilection est le C, mais je sais que pour faire la même chose en C, j'en baverais ! (Très simple sauf pour les anagrammes. J'ai trouvé comment faire, mais je le ferai en dernier.)

                        L'option 0 sert pour les cas où tu veux exclure des lettres qui n'ont pas encore été apprises.

                        Pour la partie 2) :

                        Motif à sélectionner                       ==> c 
                        
                        Recherche des mots : 
                            1. ayant le motif en début de mot
                            2. ayant le motif en fin de mot
                            3. ayant le motif dans le mot, mais ni début ni fin
                            4. ayant le motif n'importe où dans le mot
                            0. n'ayant pas le motif
                                                                   ==> 2
                        

                        Les motifs, c'est parce que tu parlais de chercher des mots qui se terminent par un T. Mais on peut choisir plusieurs lettres. Par exemple si je veux tous les mots qui finissent par "agne", je tape "agne" puis 2. Là, j'ai juste mis une lettre, 'c', parce que les mots contenant uniquement au moins une des lettres parmi C, I et R sont peu nombreux : ci, ici, cri, cric. J'ai choisi l'option 2 : motif en fin de mot. Donc je cherche, parmi les mots sélectionnés, ceux qui finissent par C. Il ne reste plus que cric.

                        Je ne sais pas si l'option 0 est utile, mais je trouve que ça ne coûte rien de la mettre.

                        Niveau programmation, ce sera pour demain voire plus tard car ça va utiliser une des spécialités du Python, le « slicing », que je ne maîtrise pas encore. Mais c'est en pensant à la recherche de motifs que je m'étais dit : le Python est fait pour ça.

                        Remarque : on peut taper "Entrée" au lieu de taper la liste des lettres. Dans ce cas il ne cherchera pas de mots selon les lettres. De même on peut taper "Entrée" au lieu de taper un motif : il ne cherchera pas de motif. Si on tape deux fois de suite "Entrée", il ne cherchera rien.

                        S'il y a quelque chose à chercher, il demande le nom du fichier de sortie. Si on tape juste "Entrée", les résultats s'afficheront dans la console. C'est la partie 3, que je n'ai pas encore écrite non plus.

                        Dernière chose : quand le traitement est terminé, le programme demande si on veut recommencer.

                        En tout cas c'est un super sujet de TP et je me suis déjà bien amusé à écrire les fonctions de recherche de mots en fonction des lettres spécifiées.

                        -
                        Edité par robun 6 avril 2020 à 21:47:32

                        • Partager sur Facebook
                        • Partager sur Twitter
                          7 avril 2020 à 13:07:09

                          Bonjour!

                          Bravo pour ton travail! 

                          Pour la recherche de mots, ton option 0 (ne contenant aucune des lettres) va m'être très très utile. Je n'avais pas mentionné cette fonctionnalité dans mon premier message, mais au fur et à mesure de l'année, les CP connaissent de plus en plus de lettres et ce sera beaucoup plus rapide d'indiquer seulement les lettres qu'ils ne connaissent pas dans la recherche, plutôt que toutes les lettres qu'ils connaissent! Donc nickel!

                          Pour le reste, tout est très clair et bien organisé, j'ai hâte de tester! 

                          Merci à toi et bonne journée!

                          • Partager sur Facebook
                          • Partager sur Twitter
                            7 avril 2020 à 21:37:00

                            A y est ! J'ai fini !

                            Je sais maintenant que "azerty" possède un anagramme dans le dictionnaire ! Je sais qu'il y autant de mots finissant par "beau" que par "belle" (sept chacun).

                            Le programme "mots" est écrit en Python 3. C'est un script en ligne de commande.

                            1) D'abord il faut copier-coller le programme dans un fichier (à l'aide d'un éditeur quelconque) qu'on nommera "mots" (ou autre chose, après tout − chez moi il s'appelle "mots", c'est explicite et vite tapé). Il faut placer ce fichier dans un certain répertoire et s'en souvenir ! Le fichier entier est dans le message suivant.

                            2) Pour le faire tourner :

                            Sous Linux :

                            Python 3 est déjà installé, il suffit donc juste de le rendre exécutable :

                            chmod u+x mots

                            Il faut aussi avoir un dictionnaire dans le même répertoire que le programme. Le dictionnaire doit s'appeler "dico" (mais on peut changer son nom dans le programme) et comporter un mot par ligne. Le plus simple est de recopier le fichier "/usr/share/dict/french" dans le répertoire du programme.

                            Ensuite, pour l'exécuter, taper :

                            ./mots

                            Sous Windows :

                            Si Python 3 n'est pas installé, il faut l'installer. Il y a des tas de tutoriels qui expliquent comment faire, par exemple https://fr.wikihow.com/installer-Python , étapes 1 à 5 concernent l'installation. (Les étapes suivantes concernent ceux qui veulent écrire des programmes en Python.)

                            Ensuite, pour faire tourner le script, il faut ouvrir une console, aller dans le répertoire où se trouve le script, et taper :

                            python mots

                            (Peut-être faut-il renommer le fichier en mots.py et, donc, taper « python mots.py » ? Je n'ai pas Windows et ne peux pas tester.)

                            -
                            Edité par robun 8 avril 2020 à 21:53:21

                            • Partager sur Facebook
                            • Partager sur Twitter
                              8 avril 2020 à 21:49:51

                              Et voici le programme :

                              #! /usr/bin/python3
                              
                              # Programme recherchant des mots dans un dictionnaire en fonction de
                              # critères portant sur les lettres et les motifs.
                              # Le dictionnaire est un fichier présent dans le même répertoire
                              # que ce programme. Il s'appelle "dico".
                              # Il doit contenir un mot par ligne et être écrit en minuscules.
                              
                              from sys import stdout
                              
                              #----------------------------------------------------------------------#
                              # Saisie du type de recherche de lettres
                              # Retourne le type de recherche de lettres
                              
                              def saisir_type_rech_lettres() :
                                  reponse_correcte = False
                                  print("\nRecherche des mots : ")
                                  print("    1. contenant au moins une des lettres")
                                  print("    2. contenant au moins une de chacune des lettres")
                                  print("    3. contenant uniquement au moins une des lettres")
                                  print("    4. contenant uniquement chacune des lettres")
                                  print("    5. anagrammes") ;
                                  print("    0. ne contenant aucune des lettres")
                                  while (not reponse_correcte) :
                                      print ("                                          ", end = "")
                                      type_rech = input(" ==> ")
                                      if type_rech not in ["0", "1", "2", "3", "4", "5"] :
                                          print("Option incorrecte")
                                      else :
                                          reponse_correcte = True
                                  return type_rech
                              
                              #----------------------------------------------------------------------#
                              # Saisie des lettres à sélectionner pour la recherche
                              # Retourne un booléen, les lettres et le type de recherche
                              
                              def saisir_lettres() :
                                  lettres = input("\nLettres à sélectionner                     ==> ")
                                  if (lettres == "") :
                                      # Pas de recherche de lettres
                                      return False, "", -1
                                  else :
                                      # Il y aura recherche de lettres
                                      type_rech = saisir_type_rech_lettres()
                                      return True, lettres.lower(), type_rech
                              
                              #----------------------------------------------------------------------#
                              # Saisie du type de recherche de motifs
                              # Retourne le type de recherche de motifs
                              
                              def saisir_type_rech_motif() :
                                  reponse_correcte = False
                                  print("\nRecherche des mots : ")
                                  print("    1. ayant le motif en début de mot")
                                  print("    2. ayant le motif en fin de mot")
                                  print("    3. ayant le motif dans le mot, mais ni début ni fin")
                                  print("    4. ayant le motif n'importe où dans le mot")
                                  print("    0. n'ayant pas le motif") ;
                                  while (not reponse_correcte) :
                                      print ("                                          ", end = "")
                                      type_rech = input(" ==> ")
                                      if type_rech not in ["0", "1", "2", "3", "4"] :
                                          print("Option incorrecte")
                                      else :
                                          reponse_correcte = True
                                  return type_rech
                              
                              #----------------------------------------------------------------------#
                              # Saisie du motif à sélectionner pour la recherche
                              # Retourne un booléen, le motif et le type de recherche
                              
                              def saisir_motif() :
                                  motif = input("\nMotif à sélectionner                       ==> ")
                                  if (motif == "") :
                                      # Pas de recherche de motif
                                      return False, "", -1
                                  else :
                                      # Il y aura recherche de motif
                                      type_rech = saisir_type_rech_motif()
                                      return True, motif.lower(), type_rech
                              
                              #----------------------------------------------------------------------#
                              # Saisie du nom de fichier de sortie
                              # Retourne un booléen et le nom du fichier de sortie
                              
                              def saisir_nom_fichier() :
                                  nom_fich = input("\nNom du fichier de sortie                   ==> ")
                                  if (nom_fich == "") :
                                      # Pas de fichier de sortie
                                      return False, ""
                                  else :
                                      # Il y aura un fichier de sortie
                                      return True, nom_fich
                              
                              #----------------------------------------------------------------------#
                              # Test des critères de lettres sur le mot courant du dictionnaire
                              # Retourne vrai si le mot répond aux critères de lettres
                              
                              def test_lettres(mot, lettres, type_rech_lettres) :
                              
                                  if type_rech_lettres == "1" :
                                      # le mot contient au moins une des lettres spécifiées
                                      # vrai dès qu'on a trouvé une lettre qui est dans le mot
                                      ok = False
                                      for c in lettres :
                                          if c in mot :
                                              ok = True
                                              break
                                  elif type_rech_lettres == "2" :
                                      # le mot contient chacune des lettres spécifiées
                                      # faux dès qu'une des lettres n'est pas dans le mot
                                      ok = True
                                      for c in lettres :
                                          if c not in mot :
                                              ok = False
                                              break
                                  elif type_rech_lettres == "3" :
                                      # le mot contient uniquement au moins une des lettres spécifiées
                                      # faux dès qu'une des lettres du mot n'est pas spécifiée
                                      ok = True
                                      for c in mot :
                                          if c not in lettres :
                                              ok = False
                                              break
                                  elif type_rech_lettres == "4" :
                                      # le mot contient uniquement chacune des lettres spécifiées
                                      # faux dès qu'une des lettres du mot n'est pas spécifiée ou
                                      # dès qu'une des lettes spécifiée n'est pas dans le mot
                                      ok = True
                                      for c in mot :
                                          if c not in lettres :
                                              ok = False
                                              break
                                      if ok :
                                          for c in lettres :
                                              if c not in mot :
                                                  ok = False
                                                  break
                                  elif type_rech_lettres == "5" :
                                      # anagrammes
                                      ok = ( sorted(lettres) == sorted(mot) )
                                  else :
                                      # le mot ne contient aucune des lettres spécifiées
                                      # faux dès qu'une lettres spécifiée est dans le mot_ok_lettres
                                      ok = True
                                      for c in lettres :
                                          if c in mot :
                                              ok = False
                                              break
                              
                                  return ok
                              
                              #----------------------------------------------------------------------#
                              # Test des critères de motif sur le mot courant du dictionnaire
                              # Retourne vrai si le mot répond aux critères de motif
                              
                              def test_motif(mot, motif, lmotif, type_rech_motif) :
                              
                                  if type_rech_motif == "1" :
                                      # le motif figure en début de mot
                                      ok = ( mot[:lmotif] == motif )
                                  elif type_rech_motif == "2" :
                                      # le motif figure en fin de mot
                                      ok = ( mot[-lmotif:] == motif )
                                  elif type_rech_motif == "3" :
                                      # le motif figure dans le mot, ni au début ni à la fin
                                      ok = ( mot.find(motif) > 0 and mot.find(motif) < len(mot) - lmotif )
                                  elif type_rech_motif == "4" :
                                      # le motif figure dans le mot, n'importe où
                                      ok = ( mot.find(motif) >= 0 )
                                  else :
                                      # le mot ne contient pas le motif
                                      ok = ( mot.find(motif) < 0 )
                              
                                  return ok
                              
                              #----------------------------------------------------------------------#
                              # Traitement principal : parcours du dictionnaire et traitement mot
                              # à mot selon les options de recherche de lettres et/ou de motif
                              # Ne retourne rien
                              
                              def traitement(lettres, type_rech_lettres, motif, type_rech_motif) :
                              
                                  sortie_fichier, nom_fichier = saisir_nom_fichier()
                              
                                  # Fichier de sortie
                                  if sortie_fichier :
                                      try :
                                          fichier = open(nom_fichier, "a")
                                      except :
                                          print("Impossible d'ouvrir ", nom_fichier)
                                          fichier = stdout
                                          print("")
                                          sortie_fichier = False
                                  else :
                                      fichier = stdout
                                      print("")
                              
                                  # Traitement
                                  lmotif = len(motif)
                                  with open("dico", "r") as dictionnaire :
                                      for ligne in dictionnaire :
                                          # normalement 1 ligne = 1 mot et le caractère \n
                                          mot = (ligne.split())[0]
                                          if recherche_lettres :
                                              mot_ok_lettres = test_lettres(mot, lettres, type_rech_lettres)
                                          else :
                                              mot_ok_lettres = True
                                          if recherche_motif :
                                              mot_ok_motif = test_motif(mot, motif, lmotif, type_rech_motif)
                                          else :
                                              mot_ok_motif = True
                                          if mot_ok_lettres and mot_ok_motif :
                                              fichier.write(mot+"\n")
                              
                                  # Fin de traitement
                                  if sortie_fichier :
                                      fichier.close()
                              
                              #----------------------------------------------------------------------#
                              #                         Programme principal                          #
                              #----------------------------------------------------------------------#
                              
                              print("\n------------------------ MOTS ------------------------")
                              
                              while True :
                              
                                  # Lecture des options
                                  recherche_lettres, lettres, type_rech_lettres = saisir_lettres()
                                  recherche_motif, motif, type_rech_motif = saisir_motif()
                              
                                  # Traitement (s'il y a quelque chose à traiter)    
                                  if recherche_lettres or recherche_motif :
                                      traitement(lettres, type_rech_lettres, motif, type_rech_motif)
                              
                                  # Est-ce qu'on recommence ?
                                  reponse = input("\nNouvelle recherche de mots ? [O]ui / [N]on ==> ")
                                  reponse = reponse.lower()
                                  if reponse != "o" :
                                      break
                              
                              print("\n--------------------- AU REVOIR ----------------------\n")

                              ---------------

                              Bug connu : si le dictionnaire n'existe pas ou n'a pas le nom correct, le programme plante. C'est parce que je ne maîtrise pas la tournure « with open(fichier) etc. » et ne sait pas où mettre la gestion de l'exception.

                              -
                              Edité par robun 8 avril 2020 à 21:53:30

                              • Partager sur Facebook
                              • Partager sur Twitter
                                8 avril 2020 à 21:53:15

                                J'ai un mac. J'ai fait tout ce que tu as dit et c'est bon le programme se lance bien. Par contre ça bug à la fin, je crois que c'est effectivement à cause du dictionnaire:

                                with open("dico", "r") as dictionnaire :

                                FileNotFoundError: [Errno 2] No such file or directory: 'dico'

                                L'extension de mon dictionnaire est dico.db... c'est pour ça que ça ne marche pas?

                                Edit: j'ai trouvé un fichier dico.text mais ça ne marche pas non plus.

                                -
                                Edité par Laurie14 8 avril 2020 à 22:11:30

                                • Partager sur Facebook
                                • Partager sur Twitter
                                  8 avril 2020 à 23:07:13

                                  Salut,

                                  la fonction open(fichier, mode) a 2 méthodes pour trouver le fichier fichier :

                                  · chemin absolu : il commence toujours par / sur Mac ou Linux

                                  · chemin relatif : mais relatif à quoi ? Sans modification, à l'emplacement du programme.

                                  Imaginons que le code de Robun se trouve dans : /Users/Laurie/CP_python/Mots/code_robun.py (chaque terme se terminant par un / est un dossier, le premier / est la racine du support de stockage. Si dans le code il y a :

                                  fichier = "dico.db"
                                  with open(fichier, 'r') as lecture:
                                      pass

                                  Il faut que dico.db se trouve dans le répertoire de Mots/, donc au même endroit que code_robun.py. Ici, Laurie, ce n'est pas le cas. Il faut trouver le chemin pour atteindre dico.db. Imaginons qu'il se trouve dans : /Libraries/Dictionnary/French/dico.db dans ce cas, on tape le chemin absolu donc le code deviendrait :

                                  fichier = "/Libraries/Dictionnary/French/dico.db"
                                  with open(fichier, 'r') as lecture:
                                      pass

                                  Il faut obligatoirement l'extension du fichier, pour open, dico et dico.txt sont différents.

                                  EDITION :

                                  Je confirme, je viens d'essayer en prenant le fichier french de /usr/share/dict/, ça fonctionne, j'ai remplacé ligne 201 :

                                  with open("dico", "r") as dictionnaire :

                                  par :

                                  with open("/usr/share/dict/french", "r") as dictionnaire :

                                  Robun, comme tu mélanges l'utilisation d'open avec ou sans with, l'utilisation est simple :

                                  traitement = open(fichier, mode)
                                  # traitement 1
                                  # traitement 2
                                  # ...
                                  # traitement n
                                  traitement.close()

                                  est pareil que :

                                  with open(fichier, mode) as traitement:
                                      # traitement 1
                                      # traitement 2
                                      # ...
                                      # traitement 3


                                  Comme idée de version plus aboutie, je te propose, Robun, un générateur de phrases. Ça impliquera de connaître la nature du mot, et sa conjugaison si nécessaire.

                                  Pour ma part, je suis intéressé pour créer l'interface graphique avec tkinter. Comme je préfère lire l'algorithme, pourras-tu m'envoyer en MP ton pseudo-code s'il te plaît ?

                                  -
                                  Edité par Le Cobriste 128 9 avril 2020 à 1:06:49

                                  • Partager sur Facebook
                                  • Partager sur Twitter
                                    8 avril 2020 à 23:34:52

                                    Laurie14 : oui, il faut le nom exact du dictionnaire. Mais tu peux le modifier dans le programme (ligne 201). Ah, Le Cobriste a très bien détaillé la démarche, merci ! Le langage Python était déjà installé sur le Mac ?

                                    Comme je préfère lire l'algorithme, pourras-tu m'envoyer en MP ton pseudo-code s'il te plaît ?

                                    Hélas, je ne fais jamais de pseudo-code, je déteste ça (je pourrais expliquer pourquoi mais c'est hors-sujet). Je passe souvent par des algorithmes écrits en français, mais là je n'en ai pas eu besoin.

                                    Faire une interface graphique serait un énorme plus en effet. Il y a deux ans, quand je m'étais mis sérieusement à Python, j'avais commencé à m'initier à Tkinter, mais j'ai galéré et je me suis interrompu là. Je crois que c'est une autre façon de programmer qui m'échappe encore.

                                    -
                                    Edité par robun 10 avril 2020 à 10:57:19

                                    • Partager sur Facebook
                                    • Partager sur Twitter
                                      10 avril 2020 à 10:56:56

                                      Comme la recherche d'anagrammes était finalement très simple, j'ai écrit un petit script pour avoir tous les anagrammes du dictionnaire. L'algorithme n'est pas optimisé : je génère la liste préalable de tous les mots du dictionnaire, puis je parcours le dictionnaire et, pour chaque mot, je compare avec chaque mot de la liste préalable. 139.719 mots à comparer à 139.719 mots, ça fait 19.521.398.961 comparaisons ! Inutile de dire que ça prend du temps... Mais c'est rigolo. (Je l'ai fait tourner toute la soirée, j'ai maintenant le fichier des 18.523 mots possédant au moins un anagramme.)

                                      La liste de tous les anagrammes du dictionnaire :

                                      abaissent : absentais abstenais 
                                      abaisser : baissera baserais rabaisse 
                                      abattent : battante 
                                      abattirent : battraient 
                                      abattis : battais 
                                      abattit : battait 
                                      abattoir : rabotait 
                                      abattons : sabotant 
                                      abattraient : rabattaient 
                                      abattrais : rabattais 
                                      ... ... ... ... ...
                                      vraie : ravie varie 
                                      vraies : aviser ravies ravise varies visera 
                                      vrais : ravis 
                                      vulgaires : vulgarise 
                                      vulgarise : vulgaires 
                                      zen : nez 
                                      zester : restez 
                                      zieuter : tueriez 
                                      zone : onze 
                                      zouave : avouez 
                                      

                                      Et le script en Python :

                                      #! /usr/bin/python3
                                      
                                      # Pour chaque mot du dictionnaire, recherche s'il y a des anagrammes.
                                      
                                      #----------------------------------------------------------------------#
                                      # 1) Création de la liste des mots du dictionnaire
                                      
                                      dictionnaire = open("dico", "r")
                                      liste_mots = [element[:-1] for element in dictionnaire.readlines()]
                                      dictionnaire.close()
                                      
                                      #----------------------------------------------------------------------#
                                      # 2) Parcours du fichier : on teste chaque mot
                                      
                                      dictionnaire = open("dico", "r")
                                      anagramme_mot_courant = False
                                      for ligne in dictionnaire :
                                          if anagramme_mot_courant :  # le mot précédent avait un ou des anagramme(s)
                                              print()                 # donc on passe à la ligne
                                          anagramme_mot_courant = False   # on n'a pas encore trouvé d'anagramme
                                          premier_anagramme = True        # s'il y a un anagramme, ce sera le premier    
                                          mot_a_comparer = ligne[:-1]
                                          # print("--> ", mot_a_comparer)
                                          liste_a_comparer = sorted(mot_a_comparer) # liste triée des lettres du mot
                                          for mot in liste_mots :
                                              if len(mot) == len(mot_a_comparer) :
                                                  if mot != mot_a_comparer and sorted(mot) == liste_a_comparer :
                                                      # c'est un anagramme
                                                      if premier_anagramme :
                                                          # on écrit le mot à comparer d'abord
                                                          print(mot_a_comparer, ":", end=" ")
                                                          premier_anagramme = False
                                                      # on écrit sur la même ligne le mot qui est son anagramme
                                                      print(mot, end=" ")
                                                      anagramme_mot_courant = True
                                      dictionnaire.close()
                                      
                                      #----------------------------------------------------------------------#
                                      

                                      On pourrait ensuite améliorer ça pour avoir la liste des mots possédant 2 anagrammes, ou 3 anagrammes, ou bien pour connaître le mot du dictionnaire qui possède le plus d'anagrammes. Il faudrait aussi proposer en option de ne pas tenir compte des accents, ce qui compliquerait drôlement...

                                      -
                                      Edité par robun 10 avril 2020 à 11:00:12

                                      • Partager sur Facebook
                                      • Partager sur Twitter
                                        11 avril 2020 à 2:58:31

                                        Salut,

                                        Je suis vraiment désolé, c'est sale, mais, je suis crevé, j'éditerai plus tard si le code est mal compris.

                                        Je me suis basé sur ton code, et à force d'essais, j'ai remarqué que la fonction comparer(mot, autre_mot) est plus rapide que la fonction sorted(mot) == sorted(autre_mot).

                                        Voici le code :

                                        from time import time
                                        
                                        def comparer(mot, autre_mot):
                                            for lettre in mot:
                                                if lettre not in autre_mot:
                                                    return False
                                            return True
                                        
                                        fichier = "/usr/share/dict/french"
                                        
                                        with open(fichier, "r") as dictionnaire:
                                            liste_mots = [element.rstrip() for element in dictionnaire.readlines()]
                                        
                                        liste_mots = liste_mots[:8500]
                                         
                                        #----------------------------------------------------------------------#
                                        # 2) Parcours du fichier : on teste chaque mot
                                        
                                        dictionnaire = open(fichier, "r")
                                        anagramme_mot_courant = False
                                        debut = time()
                                        compteur = 0
                                        for _ in range(8500):
                                            mot_a_comparer = dictionnaire.readline().rstrip()
                                        
                                            #if anagramme_mot_courant :  # le mot précédent avait un ou des anagramme(s)
                                                #print()                 # donc on passe à la ligne
                                            anagramme_mot_courant = False   # on n'a pas encore trouvé d'anagramme
                                            premier_anagramme = True        # s'il y a un anagramme, ce sera le premier   
                                            #mot_a_comparer = ligne[:-1]
                                            # print("--> ", mot_a_comparer)
                                            #liste_a_comparer = sorted(mot_a_comparer) # liste triée des lettres du mot
                                            for mot in liste_mots :
                                                if len(mot) == len(mot_a_comparer) :
                                                    if mot != mot_a_comparer and comparer(mot, mot_a_comparer):
                                                        # c'est un anagramme
                                                        if premier_anagramme :
                                                            # on écrit le mot à comparer d'abord
                                                 #           print(mot_a_comparer, ":", end=" ")
                                                            premier_anagramme = False
                                                        # on écrit sur la même ligne le mot qui est son anagramme
                                                  #      print(mot, end=" ")
                                                        anagramme_mot_courant = True
                                        print(time() - debut)
                                        
                                        dictionnaire.close()


                                        Pour les 8500 premiers mots, avec sorted(), ça prenait environ 25 secondes, et 19 secondes avec ma fonction.

                                        Quoi qu'il en soit, un tel programme n'est pas judicieux car très gourmand en ressources. Le mieux est un programme où on demande les anagrammes d'un mot.

                                        -
                                        Edité par Le Cobriste 128 11 avril 2020 à 2:59:13

                                        • Partager sur Facebook
                                        • Partager sur Twitter
                                          11 avril 2020 à 11:46:18

                                          Salut,

                                          À un moment, j'avais écrit un truc qui cherchait les anagrammes. L'idée pour avoir un bon algorithme, c'est de trouver une fonction p qui est invariante par anagramme (ie si deux mots w et w' sont des anagrammes, alors p(w) = p(w')). Et ensuite on stocke tous les mots du dictionnaire dans une table de hachage dont les éléments sont des listes de mots. On stocke w à la case p[w].

                                          Reste à trouver de bonnes fonctions p. Une première fonction associe à chaque mot le nombre de fois que chaque lettre est présente dans ce mot. Une encore plus efficace est d'associer à chaque lettre a un nombre premier, et associe alors à un mot le produit des nombres premiers associés à ses lettres. L'unicité de la décomposition en nombres premiers assure que deux mots sont associés au même nombre si et seulement si ce sont des anagrames. En Ruby ça peut donner ça.

                                          require 'prime'
                                          
                                          class String
                                            PRIMES = Prime.each
                                            LETTERS_VALUE = Hash.new { |h, k| h[k] = PRIMES.next }
                                          
                                            def value
                                              each_char.map { |c| LETTERS_VALUE[c] }.reduce(:*)
                                            end
                                          end
                                          
                                          
                                          def create_prime_value_hash(dictionary)
                                            dictionary.each.with_object(Hash.new { |h, k| h[k]=[] }) do |w, h|
                                              h[w.value] &lt;&lt; w
                                            end
                                          end
                                          
                                          def anagrams(dictionary, words)
                                            hash = create_prime_value_hash(dictionary)
                                            words.each.with_object({}) { |w, h| h[w] = (hash[w.value] - [w]).sort }
                                          end
                                          
                                          def main(filename)
                                            dictionary = File.readlines(filename).map(&amp;:chomp)
                                            result = anagrams(dictionary, dictionary)
                                            dictionary.each do |w|
                                              print "#{w} : "
                                              result[w].each { |w| print "#{w} " }
                                              puts
                                            end
                                          rescue Errno::ENOENT =&gt; e
                                            puts "Failed to load dictionary: #{e.message}"
                                          end
                                          
                                          main('/usr/share/dict/french')
                                          

                                          EDIT : faute à l'éditeur d'OC, &gt; à remplacer par > et &lt; à remplacer par <.

                                          -
                                          Edité par yo@n97one 12 avril 2020 à 18:24:31

                                          • Partager sur Facebook
                                          • Partager sur Twitter
                                          Tutoriel Ruby - Bon tutoriel C - Tutoriel SDL 2 - Python avancé - Faîtes un zeste, devenez des zesteurs
                                            11 avril 2020 à 18:03:53

                                            Salut,

                                            C’est une très bonne piste Yoan, en faisant quelques recherches sur les anagrammes j’étais tombé sur la méthode avec les nombres premiers. 

                                            • Partager sur Facebook
                                            • Partager sur Twitter
                                              12 avril 2020 à 13:38:25

                                              L'idée de Yo@n97one me plaît beaucoup. Il faudrait un dictionnaire qui ressemblerait à

                                              code = {'a':2, 'b':3, 'c':5, 'd':7, 'e':11, 'f':13, 'g':17, ...}

                                              et pour calculer le code du mot, on multiplierait entre eux les codes de chaque lettre distincte :

                                              >>> mot = "efface"
                                              >>> codemot = 1
                                              >>> for c in mot :
                                              ...     codemot *= code[c]
                                              ... 
                                              >>> print(codemot)
                                              204490
                                              

                                              Deux mots ayant le même code sont forcément anagrammes (par unicité de la décomposition en facteurs premiers). Voilà une bonne idée pour améliorer mon programme, et ça permet de s'entraîner avec le concept de dictionnaire...

                                              -
                                              Edité par robun 12 avril 2020 à 13:51:59

                                              • Partager sur Facebook
                                              • Partager sur Twitter
                                                12 avril 2020 à 14:42:25

                                                Et on peut éviter de calculer le produit de toutes les lettres du deuxième mot à comparer. En le triant dans l’ordre décroissant et dès que le produit de celui-ci dépasse le produit des lettres du premier mot : ce n’est pas un anagramme.

                                                Cab vs ace

                                                cab : 5*3*2 = 30

                                                ace devient cea

                                                5*11 = 55 > 30. Stop. Ace n’est pas l’anagramme de cab. 

                                                • Partager sur Facebook
                                                • Partager sur Twitter
                                                  12 avril 2020 à 15:13:51

                                                  Attention, trier le mot donne une moins bonne complexité asymptotique. On pourrait se dire qu'en pratique on rattrape ça en s'arrêtant quand le produit dépasse, mais en fait non, puisque trier nous demandera quand même de parcourir tout le mot en faisant des comparaisons et des échanges (du O(Nkln(k)) avec k le nombre maximum de lettres d'un mot et N le nombre de mots plus ensuite du O(Nk) pour les produits) alors qu'on a juste du O(Nk) si on fait juste les produits).

                                                  En fait, si on doit trier le mot, autant prendre comme propriété invariante par anagrammes la liste triée des lettres du mot. Ainsi, on a juste à comparer les éléments des listes jusqu'à trouver une lettre différente et on ne s'embête pas avec un produit de nombres premiers.

                                                  De plus, autant calculer tous les produits une unique fois (et stocker chaque mot à la case x du dictionnaire avec x le produit de ses lettres). Ceci permet d'obtenir rapidement les anagrammes de plusieurs mots. Par exemple, dans le code que j'ai donné, je calcule les anagrammes de chaque mot et sur un dictionnaire de plusieurs centaines de milliers de mots en moins d'une seconde.

                                                  -
                                                  Edité par yo@n97one 12 avril 2020 à 15:20:51

                                                  • Partager sur Facebook
                                                  • Partager sur Twitter
                                                  Tutoriel Ruby - Bon tutoriel C - Tutoriel SDL 2 - Python avancé - Faîtes un zeste, devenez des zesteurs
                                                    12 avril 2020 à 17:14:25

                                                    Oui, Tu as raison pour ton premier paragraphe, je réfléchissais quant à l'utilité de l'opération de tri. Je ne trouvais pas cela optimal, donc, j'ai laissé tomber.

                                                    Je ne sais pas lire le Ruby et si tu ne sais pas lire le Python, on va pas aller loin. Mais, voici ce que j'ai fait, en me basant sur le fichier fourni par Linux, je ne sais pas s'il existe sur macOS :

                                                    import math
                                                    
                                                    def produit_des_premiers(mot, correspondance_lettres_nombres_premiers):
                                                        produit = 1
                                                        for lettre in mot:
                                                            produit *= correspondance_lettres_nombres_premiers[lettre]
                                                        return produit
                                                    
                                                    def est_un_nombre_premier(nombre):
                                                        racine_superieure_du_nombre = int(math.sqrt(nombre))
                                                        for i in range(2, racine_superieure_du_nombre):
                                                            if nombre % i == 0:
                                                                return False
                                                        return True
                                                    
                                                    def est_un_anagramme(mot, autre_mot, dictionnaire_des_produits):
                                                        if dictionnaire_des_produits[mot] == dictionnaire_des_produits[autre_mot]:
                                                            return True
                                                        return False
                                                    
                                                    fichier = "/usr/share/dict/french"
                                                    
                                                    lettres = [
                                                        ['a', 'à', 'â', 'ä'],
                                                        'b',
                                                        ['c', 'ç'],
                                                        'd',
                                                        ['e', 'é', 'è', 'ê', 'ë'],
                                                        'f',
                                                        'g',
                                                        'h',
                                                        ['i', 'î', 'ï'],
                                                        'j',
                                                        'k',
                                                        'l',
                                                        'm',
                                                        'n',
                                                        ['o', 'ô', 'ö'],
                                                        'p',
                                                        'q',
                                                        'r',
                                                        's',
                                                        't',    
                                                        ['u', 'ù', 'û', 'ü'],
                                                        'v',    
                                                        'w',
                                                        'x',
                                                        'y',
                                                        'z',
                                                        '-',
                                                        ' ',
                                                        'œ',
                                                        'æ',
                                                        '.',
                                                        "'",
                                                    ]
                                                    
                                                    correspondance_lettres_nombres_premiers = {}
                                                    
                                                    nombres_premiers_26 = []
                                                    compteur = 0
                                                    total = len(lettres)
                                                    nombre = 2
                                                    
                                                    while compteur < total:
                                                        if est_un_nombre_premier(nombre):
                                                            nombres_premiers_26.append(nombre)
                                                            compteur += 1
                                                        nombre += 1
                                                    
                                                    for cle, valeur in zip(lettres, nombres_premiers_26):
                                                        if isinstance(cle, list):
                                                            for i in cle:
                                                                correspondance_lettres_nombres_premiers[i] = valeur
                                                        else:
                                                            correspondance_lettres_nombres_premiers[cle] = valeur
                                                    
                                                    with open(fichier, 'r') as traitement_de_lecture:
                                                        mots = {}
                                                        for ligne in traitement_de_lecture:
                                                            mot = ligne.rstrip()
                                                            produit_mot = produit_des_premiers(mot, correspondance_lettres_nombres_premiers)
                                                            mots[mot] = produit_mot

                                                    Mon dictionnaire mots se présente ainsi : {"mot": produit de ses lettres}.

                                                    Je n'ai pas fait le print() ligne par ligne comme Robun.

                                                    • Partager sur Facebook
                                                    • Partager sur Twitter
                                                      12 avril 2020 à 18:13:59

                                                      Plutôt que d'associer à ton mot son produit, je te conseille d'associer à un nombre la liste des mots pour qui il est le produit des lettres. Ainsi, tous les mots présents dans une case sont des anagrammes l'un de l'autre (on se retrouve en gros avec des classes d'équivalence). Récupérer les anagrammes d'un mot consiste alors juste à regarder dans la bonne case.

                                                      dic = {}
                                                      for ligne in traitement_de_lecture:
                                                              mot = ligne.rstrip()
                                                              produit_mot = produit_des_premiers(mot, correspondance_lettres_nombres_premiers)
                                                              dic.setdefault(produit_mot, []).append(mot)
                                                      
                                                      • Partager sur Facebook
                                                      • Partager sur Twitter
                                                      Tutoriel Ruby - Bon tutoriel C - Tutoriel SDL 2 - Python avancé - Faîtes un zeste, devenez des zesteurs
                                                        12 avril 2020 à 19:10:11

                                                        J'avais l'idée de rassembler les anagrammes entre eux, mais, je ne savais pas comment faire. J'ai "étudié" le fonctionnement de la méthode setdefault() d'un dictionnaire. Au premier abord, je n'ai pas trouvé cela très intuitif, mais, ton exemple est simple à comprendre :

                                                        Si produit_mot n'existe pas, ce qui est le cas lors du premier mot correspondant, on crée sa valeur correspondante qui est une liste, puis on y ajoute ce premier mot. Si produit_mot existe, on ajoute le mot à la liste. Tu confirmes ?

                                                        Par contre, la fonction est_un_anagramme() devient fausse.

                                                        De base, le mot est la clé de mon dico, or, c'est le produit qui en devient la clé dans le tiens. Ça implique de se positionner dans la clé du premier mot, et vérifier si le deuxième mot est dans la liste. Donc, il faut en amont calculer le produit du premier mot. Cela fait une opération supplémentaire.

                                                        Dans le fichier que j'utilise, il y a environ 145K mots. Avec ma méthode, le dico a 145K correspondances, et le tiens, 115K. Est-ce que les 21 % d'optimisation sont vraiment intéressantes puisqu'il faut ajouter l'opération de calcul du produit du mot. Quand on cherche un anagramme d'un mot, humainement, la première donnée qu'on entre est le mot, pas son produit.

                                                        -
                                                        Edité par Le Cobriste 128 12 avril 2020 à 19:30:20

                                                        • Partager sur Facebook
                                                        • Partager sur Twitter
                                                          12 avril 2020 à 20:15:10

                                                          Oui c'est ça pour setdefault.

                                                          > De base, le mot est la clé de mon dico, or, c'est le produit qui en devient la clé dans le tiens. Ça implique de se positionner dans la clé du premier mot, et vérifier si le deuxième mot est dans la liste. Donc, il faut en amont calculer le produit du premier mot. Cela fait une opération supplémentaire.

                                                          On va se placer au moment où on a déjà tout calculé. Et on veut les anagrammes de m mots. En ayant les produits en clés, pour chaque mot dont on veut l'anagramme on calcule le produit (O(mk) avec k la longueur maximale des mots) et ensuite on a tous les anagrammes en allant à la bonne case. En ayant les mots en clés, il faut parcourir tout le dictionnaire pour chaque mot et trouver ceux à qui on a associé la même valeur (donc O(nm) avec n le nombre de mots du dictionnaire). Et le nombre de mots du dictionnaire (n) est plutôt grand devant le nombre maximum de lettres d'un mot (k) ; calculer le produit d'un mot est une opération négligeable.

                                                          Avoir les mots en clé est mieux si on veut juste savoir si un mot est un anagramme d'un autre. Mais si c'est juste ça qu'on veut, pas la peine de s'embêter avec un dictionnaire. Pour accéder à la case d'un mot dans le dictionnaire, il faut hacher le mot (et donc on le parcourt quand même), je ne pense pas que ce soit beaucoup plus rapide (et peut-être même que c'est moins rapide) que de faire le produit pour les deux mots et de les comparer.

                                                          Néanmoins, si on voulait aussi ne pas s'embêter en recalculant le produit des mots (ou parce qu'on a un nombre très grand de mots grands) on pourrait garder les deux dictionnaires. Le dictionnaire prod_mot qui à un mot associe son produit et le dictionnaire anagram qui à un produit associe la liste des mots qui ont ce produit. On peut alors avoir tous les anagrammes de mot avec anagram[prod_mot[mot]], on peut également savoir si deux mots sont anagrames l'un de l'autre avec prod_mot, etc.

                                                          -
                                                          Edité par yo@n97one 12 avril 2020 à 20:17:55

                                                          • Partager sur Facebook
                                                          • Partager sur Twitter
                                                          Tutoriel Ruby - Bon tutoriel C - Tutoriel SDL 2 - Python avancé - Faîtes un zeste, devenez des zesteurs
                                                            12 avril 2020 à 21:25:15

                                                            Je comprends à peu près, ça fait un moment que j'ai laissé tomber les complexités.

                                                            Je te fournis une évolution de mon code, regarde juste la fonction est_un_anagramme(), si elle n'est pas optimale :

                                                            import math
                                                            
                                                            def produit_des_premiers(mot, correspondance_lettres_nombres_premiers):
                                                                produit = 1
                                                                for lettre in mot:
                                                                    produit *= correspondance_lettres_nombres_premiers[lettre]
                                                                return produit
                                                            
                                                            def est_un_nombre_premier(nombre):
                                                                racine_superieure_du_nombre = int(math.sqrt(nombre))
                                                                for i in range(2, racine_superieure_du_nombre):
                                                                    if nombre % i == 0:
                                                                        return False
                                                                return True
                                                            
                                                            def est_un_anagramme(mot, autre_mot, correspondance_lettres_nombres_premiers, dictionnaire_des_produits):
                                                                produit_mot = produit_des_premiers(mot, correspondance_lettres_nombres_premiers)
                                                                if autre_mot in dictionnaire_des_produits[produit_mot]:
                                                                    return True
                                                                return False
                                                            
                                                            fichier = "/usr/share/dict/french"
                                                            
                                                            lettres = [
                                                                ['a', 'à', 'â', 'ä'],
                                                                'b',
                                                                ['c', 'ç'],
                                                                'd',
                                                                ['e', 'é', 'è', 'ê', 'ë'],
                                                                'f',
                                                                'g',
                                                                'h',
                                                                ['i', 'î', 'ï'],
                                                                'j',
                                                                'k',
                                                                'l',
                                                                'm',
                                                                'n',
                                                                ['o', 'ô', 'ö'],
                                                                'p',
                                                                'q',
                                                                'r',
                                                                's',
                                                                't',    
                                                                ['u', 'ù', 'û', 'ü'],
                                                                'v',    
                                                                'w',
                                                                'x',
                                                                'y',
                                                                'z',
                                                                '-',
                                                                ' ',
                                                                'œ',
                                                                'æ',
                                                                '.',
                                                                "'",
                                                            ]
                                                            
                                                            correspondance_lettres_nombres_premiers = {}
                                                            
                                                            nombres_premiers_26 = []
                                                            compteur = 0
                                                            total = len(lettres)
                                                            nombre = 2
                                                            
                                                            while compteur < total:
                                                                if est_un_nombre_premier(nombre):
                                                                    nombres_premiers_26.append(nombre)
                                                                    compteur += 1
                                                                nombre += 1
                                                            
                                                            for cle, valeur in zip(lettres, nombres_premiers_26):
                                                                if isinstance(cle, list):
                                                                    for i in cle:
                                                                        correspondance_lettres_nombres_premiers[i] = valeur
                                                                else:
                                                                    correspondance_lettres_nombres_premiers[cle] = valeur
                                                            
                                                            with open(fichier, 'r') as traitement_de_lecture:
                                                                mots = {}
                                                                for ligne in traitement_de_lecture:
                                                                    mot = ligne.rstrip()
                                                                    produit_mot = produit_des_premiers(mot, correspondance_lettres_nombres_premiers)
                                                                    mots.setdefault(produit_mot, []).append(mot)

                                                            J'ai, ensuite, fait répéter 1.5M de fois l'opération de recherche d'anagrammes entre deux mots. Dans mon premier code, sur mon ordi (iMac 2010 bas de gamme 27", OS : Xubuntu 18.04 LTS), ça a mis 337 ms. Avec le code ci-dessus, la même opération a pris 1478 ms.

                                                            Si je ne dis pas de connerie, et n'hésite pas à me corriger, tu maîtrises mieux les complexités algorithmiques, chercher la valeur d'une clé d'un dico c'est du O(1).

                                                            Yoan dit : "Avoir les mots en clé est mieux si on veut juste savoir si un mot est un anagramme d'un autre." Oui, c'est ça. Pour la suite, je suis d'accord. Cependant, la liste des mots est dans un fichier, lire le fichier avec with open() permet de le "placer" dans la RAM qui est bien plus rapide. J'évite de créer une liste qui contiendra les mots pour ensuite la parcourir pour calculer le produit d'un mot. D'ailleurs, l'opération mot in liste n'est pas aussi optimal que dico[mot] qui, en plus, donnera le produit du mot.

                                                            Dans la suite de ce que je cite, tu veux dire qu'on peut se limiter à ceci :

                                                            est_un_anagramme(mot, autre_mot, correspondance_lettres_nombres_premiers):
                                                                if produit_des_premiers(mot, correspondance_lettres_nombres_premiers) == produit_des_premiers(autre_mot, correspondance_lettres_nombres_premiers):
                                                                    return True
                                                                return False


                                                            Pigé pour le dernier paragraphe, malgré la récursion qui me provoque des maux de têtes :

                                                            import math
                                                            import time
                                                            
                                                            def produit_des_premiers(mot, correspondance_lettres_nombres_premiers):
                                                                produit = 1
                                                                for lettre in mot:
                                                                    produit *= correspondance_lettres_nombres_premiers[lettre]
                                                                return produit
                                                            
                                                            def est_un_nombre_premier(nombre):
                                                                racine_superieure_du_nombre = int(math.sqrt(nombre))
                                                                for i in range(2, racine_superieure_du_nombre):
                                                                    if nombre % i == 0:
                                                                        return False
                                                                return True
                                                            
                                                            def est_un_anagramme(mot, autre_mot, dictionnaire_des_produits):
                                                                if dictionnaire_des_produits[mot] == dictionnaire_des_produits[autre_mot]:
                                                                    return True
                                                                return False
                                                            
                                                            fichier = "/usr/share/dict/french"
                                                            
                                                            lettres = [
                                                                ['a', 'à', 'â', 'ä'],
                                                                'b',
                                                                ['c', 'ç'],
                                                                'd',
                                                                ['e', 'é', 'è', 'ê', 'ë'],
                                                                'f',
                                                                'g',
                                                                'h',
                                                                ['i', 'î', 'ï'],
                                                                'j',
                                                                'k',
                                                                'l',
                                                                'm',
                                                                'n',
                                                                ['o', 'ô', 'ö'],
                                                                'p',
                                                                'q',
                                                                'r',
                                                                's',
                                                                't',    
                                                                ['u', 'ù', 'û', 'ü'],
                                                                'v',    
                                                                'w',
                                                                'x',
                                                                'y',
                                                                'z',
                                                                '-',
                                                                ' ',
                                                                'œ',
                                                                'æ',
                                                                '.',
                                                                "'",
                                                            ]
                                                            
                                                            correspondance_lettres_nombres_premiers = {}
                                                            
                                                            nombres_premiers_26 = []
                                                            compteur = 0
                                                            total = len(lettres)
                                                            nombre = 2
                                                            
                                                            while compteur < total:
                                                                if est_un_nombre_premier(nombre):
                                                                    nombres_premiers_26.append(nombre)
                                                                    compteur += 1
                                                                nombre += 1
                                                            
                                                            for cle, valeur in zip(lettres, nombres_premiers_26):
                                                                if isinstance(cle, list):
                                                                    for i in cle:
                                                                        correspondance_lettres_nombres_premiers[i] = valeur
                                                                else:
                                                                    correspondance_lettres_nombres_premiers[cle] = valeur
                                                            
                                                            with open(fichier, 'r') as traitement_de_lecture:
                                                                anagrammes = {}
                                                                mots = {}
                                                                for ligne in traitement_de_lecture:
                                                                    mot = ligne.rstrip()
                                                                    produit_mot = produit_des_premiers(mot, correspondance_lettres_nombres_premiers)
                                                                    mots[mot] = produit_mot
                                                                    anagrammes.setdefault(produit_mot, []).append(mot)
                                                            



                                                            • Partager sur Facebook
                                                            • Partager sur Twitter
                                                              12 avril 2020 à 21:47:40

                                                              Oui c'est normal que le premier code soit plus rapide vu qu'on veut juste savoir si deux mots sont des anagrammes. Essaie des tests om tu veux trouver tous les anagrammes d'un mot dans le dictionnaire (ou même pire connaître tous les anagrammes dans le dictionnaire de tous les mots du dictionnaire).


                                                              On dit que trouver la valeur associée à une clé dans un dictionnaire est en O(1). Mais en fait, c'est un peu faux, il faudrait plutôt dire que c'est en O(|clé|). Il faut bien lire toute la clé pour la connaître. Et donc dans le cas d'une chaîne de caractère il faut la parcourir (et donc on ne gagne pas beaucoup à la parcourir et faire le produit et peut-être même qu'on y perd).


                                                              Et oui, on peut alors remplacer par la fonction que tu as donné et se passer du dictionnaire.


                                                              def est_un_anagramme(mot, autre_mot, correspondance_lettres_nombres_premiers):
                                                                  if produit_des_premiers(mot, correspondance_lettres_nombres_premiers) == produit_des_premiers(autre_mot, correspondance_lettres_nombres_premiers):
                                                                      return True
                                                                  return False
                                                              

                                                              Essaie les tests entre ta fonction d'origine et cette fonction.


                                                              Je vais écrire un code Python et faire des tests moi aussi. :)

                                                              -
                                                              Edité par yo@n97one 12 avril 2020 à 21:47:58

                                                              • Partager sur Facebook
                                                              • Partager sur Twitter
                                                              Tutoriel Ruby - Bon tutoriel C - Tutoriel SDL 2 - Python avancé - Faîtes un zeste, devenez des zesteurs

                                                              [Programme] Besoin aide ou développeur

                                                              × Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
                                                              • Editeur
                                                              • Markdown