Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#1 02-11-2011 17:05:25

karlun
Membre
Inscription : 05-05-2010
Messages : 216

(Python) jeux de lettres.

Bonjour,

Suite au petit « jeu sans nom » proposé par Nerosson, j'ai eu l'idée de faire travailler Python afin de construire une liste de mots possibles de 2,3,4,5,6 lettres de longueur à partir d'un mot de 9 lettres (j'ai pas eu le courage de continuer jusqu'à 9).
Faut dire qu'il faut analyser 46656 combinaisons de 6 lettres et voir si elles font partie du dictionnaire français. Ces 6 lettres appartiennent au mot « Allemagne » inspiré du jeu sans nom de Nerosson.
Pour les neufs lettres... pfffff !
C'est pas le programme qui pose problème, c'est le temps qu'il faut avoir pour l'analyse des résultats n'ayant aucune base de donnée sous la main.
Pour ce qui est du programme, j'ai limité l'impression des résultats; l'affichage prend beaucoup trop de temps.

Je suis sûr qu'il y aura des remarques sur la méthode et aussi de bonnes suggestions... je suis preneur.

Voici (version par étapes),


# usr/bin/env python
#-*- coding: cp1252 -*-
from textwrap import wrap
sol=[]
mot='allemagne'
lettres=wrap(mot,1)
print len(lettres)
for i in xrange(0,len(lettres),1):
    for li in lettres:
        sol.append(li+lettres[i])
sol=list(set(sol))
#print sol,len(sol)
#***********3 lettres****************
trav=sol
sol=[]
for i in xrange(0,len(lettres),1):
    for li in trav:
        sol.append(li+lettres[i])
sol=list(set(sol))
#print sol, len (sol)
#***********4 lettres *****************
trav=sol
sol=[]
for i in xrange(0,len(lettres),1):
    for li in trav:
        sol.append(li+lettres[i])
sol=list(set(sol))
#print sol, len (sol)
#***********5 lettres *****************
trav=sol
sol=[]
for i in xrange(0,len(lettres),1):
    for li in trav:
        sol.append(li+lettres[i])
sol=list(set(sol))
#print sol, len (sol)
#***********6 lettres *****************
trav=sol
sol=[]
for i in xrange(0,len(lettres),1):
    for li in trav:
        sol.append(li+lettres[i])
sol=list(set(sol))
print sol[45665:], len (sol)
 

En plus court (la même démarche mise en boucle):

# usr/bin/env python
#-*- coding: cp1252 -*-
from textwrap import wrap

mot,x='allemagne',0
lettres=wrap(mot,1)
trav=lettres
while x<=len(lettres)-2: #nbre de lettres du mot
    sol=[]
    for i in xrange(0,len(lettres),1):
        for li in trav:
            sol.append(li+lettres[i])
    trav=list(set(sol))
    x+=1
    print
    print sol[:10], len (trav)
 

(ici ce ne seront que les 10 premiers résultats pour chaque longueur qui seront affichés)

Voici ce qui s'affiche:

['aa', 'el', 'en', 'ae', 'ag', 'ee', 'eg', 'ea', 'al', 'an'] 36

['aln', 'all', 'alm', 'alg', 'ale', 'ala', 'nla', 'mnl', 'mnm', 'llm'] 216

['mgnn', 'emmn', 'enle', 'eean', 'aage', 'lnmm', 'lnml', 'gana', 'negn', 'nmea'] 1296

['elegm', 'angnn', 'angnm', 'angnl', 'angng', 'angne', 'angna', 'emlee', 'emleg', 'emlea'] 7776

['aggeml', 'nallen', 'ngeneg', 'nallel', 'nallem', 'nallea', 'nalleg', 'nallee', 'mnnmmg', 'mlamae'] 46656

['gegeaaa', 'gallgmn', 'gegeaae', 'gegeaag', 'nglaanl', 'engmgen', 'gegeaam', 'gegeaal', 'ggeneee', 'nnmeell'] 279936

['eamnmaga', 'lmemlmgl', 'eamnmage', 'eamnmagg', 'lmnggman', 'eamnmagl', 'eamnmagm', 'eamnmagn', 'gnleggen', 'nnemmaga'] 1679616

['mmaellega', 'alnlmglam', 'mmnlaenln', 'gglagaaan', 'galnenaae', 'emeemnnan', 'aenmealem', 'eenmammln', 'ammgngeel', 'ammgngeem'] 10077696


Quelques mots de
6 lettres:

magana,langea,magane,manage,gagmen,annale,engage,gamela,lamage,emmena,engame,engama,gagman,mangea,malaga.
(Pas manège car il y a l'accent)

5 lettres:

malle,lemme,angle,gamme,gamma,amena,galle,gemma,gagea,gagne,gagna,ganga,magne,magna,glane,glana,agame,maman,mange,lange,anale,magma,manga,nagea,annal,nanan.

4 lettres:

elle,mana,mage,gage,gaga,gela,lame,mena,nage,gale,gala,ange,alla,gang,lama,nana,anal.

3 lettres:

aga,age,mal,ana,mlm,gag,gan,gel,nlm,ale,alm.

2 lettres:

en,ag,al,an,le,nl,nm,la na, lm,ne,ng,am,me,mg,ma,mm,ml.

A+-*/

Dernière modification par karlun (03-11-2011 12:34:46)


Qui trouve, cherche.

Hors ligne

#2 03-11-2011 16:52:24

karlun
Membre
Inscription : 05-05-2010
Messages : 216

Re : (Python) jeux de lettres.

Bonjour,

Pour me rapprocher via Python des solutions au  « jeu qui n'as pas de nom » initié par Nerosson, Fallait que les permutations des lettres puissent se faire sans répétitions.

L'affaire est dans la boite.

Voici:


# usr/bin/env python
# -*- coding: cp1252 -*-
from textwrap import wrap
     
mot,x,n='argentin',0,[]
lettres=wrap(mot,1)
print lettres
for t in lettres:
    n.append(lettres.count(t))
print n
trav=lettres
while x<=len(lettres)-2: #nbre de lettres du mot
    sol=[]
    for i in xrange(0,len(lettres),1):
        for li in trav:
            p=li+lettres[i]
            pu=p.count(lettres[i])
            if pu<=n[i]:
                sol.append(li+lettres[i])
    trav=list(set(sol))
    x+=1
print
print trav, len (trav)
 

Voici quelques solutions parmi d'autres  (elles dépendent du choix de la lettre enlevée)

Pour le mot « allemagne » il n'y a pas de solution. En enlevant une quelconque des lettres composant le mot il n'y a aucun autre mot qui ne possède une voyelle accentuée.

Pour le mot « argentine »:

-8 lettres  [argentin]             (j'ai enlevé la lettre finale)
    grainent et argentin   (mais ça on peut pas).
-7 lettres  [argenti]             (j'ai enlevé la lettre finale)
    grenait, agirent, granite, ingrate, gratine, gantier.
-6 lettres  [argent]             (j'ai enlevé la lettre finale)
    garent, grena, ragent,argent,ganter
-5 lettres  [argen]             (j'ai enlevé la lettre finale)
    grena,nager, range.
-4 lettres  [arge]                 (j'ai enlevé la lettre finale)
    rage, gare.
-3 lettres  [are]                 (j'ai enlevé la lettre g )
    are
-2 lettres  [ar]                 (j'ai enlevé la lettre finale )
    ra

Pour le mot « birmanie »:
       
-7 lettres  [irmanie]            (j'ai enlevé la 1° lettre )
    minerai.
-6 lettres  [rmanie]            (j'ai enlevé la 1° lettre )
    manier, aminer, animer, minera, ranime, marine.
-5 lettres  [manie]            (j'ai enlevé la 1° lettre )
    amine,anime,manie, menai.
-4 lettres  [anie]                (j'ai enlevé la 1° lettre )
    aine.
-3 lettres  [nie]                (j'ai enlevé la 1° lettre )
    nie
-2 lettres  [ni]            (j'ai enlevé la dernière lettre )
    ni

Vive Python.

A+-*/

PS: programme brut de décoffrage à affiner sans doute.

Dernière modification par karlun (07-11-2011 19:34:03)


Qui trouve, cherche.

Hors ligne

#3 09-11-2011 18:09:22

tibo
Membre expert
Inscription : 23-01-2008
Messages : 1 097

Re : (Python) jeux de lettres.

Salut,

Je m'y suis essayé aussi.

Normalement, ça donne toutes les suites de mots possibles pour arriver à un mot de deux lettres.
Mais c'est très long, de l'ordre de [tex]4n^n[/tex] opérations (si j'ai bien calculé) avec n le nombre de lettre du mot de départ.
Je n'ai pas beaucoup commenté, je le ferai si demandé
Au début, dans la partie ou on lit les mots dans un fichier, je ne suis pas très sûr de moi, je n'utilise que rarement des fichiers texte avec python
Le dictionnaire que j'utilise est le dernier dictionnaire du scrable, donc sans accent ni majuscule


import sqlite3

# importation des mots de la langue francaise
# et mis dans la liste dico

# chez moi les mots sont dans une base de donnees
bdd=sqlite3.connect("/home/kirq/Documents/mot/motBdd")
cur=bdd.cursor()
cur.execute("SELECT mot FROM liste")
lis=cur.fetchall()
dico=[]        
for i in lis:
  dico.append(i[0])

# si chez vous les mots sont dans un fichier texte,
# commentez toutes les lignes au dessus et decommentez les 3 lignes en dessous
#fil=open("mot.txt",'r')
#dico=fil.readlines()
#fil.closes()

####################################

# donne tout les anagrammes de mo moins une lettre
# puis garde ceux qui sont dans dico
def rech(mo):
  le=[]
  so=[]
  for i in mo:
    le.append(i)
    so.append(i)

  x=0
  while x<len(le)-2:
    mi=[]
    for i in so:
      for j in le:
        mi.append(i+j) 
    so=mi
    x=x+1

  sol=[]
  for i in so:
    if i in dico and not(i in sol):
      sol.append(i)

  #print mo, "donne", sol
  return sol

#######################"

dep=raw_input("Entrer le mot de depart :\n")

solinter=[[dep]]
x=0
while x<len(dep)-2:
  tra=[]
  for i in solinter:
    re=rech(i[-1])
    for j in re:
      tra.append(i+[j])
  solinter=tra
  x=x+1
 
  #print "solution intermediare = ",solinter

solution=[]
for i in solinter:
  if len(i) == len(dep)-1:
    solution.append(i)

print "Les solutions possibles pour le mot", dep, "sont :"
for i in solution:
  print i
if solution==[]:
  print "aucune"
 

Dernière modification par tibo (09-11-2011 18:14:57)


A quoi sert une hyperbole?
----- A boire de l'hypersoupe pardi !

Hors ligne

#4 09-11-2011 20:49:03

Fred
Administrateur
Inscription : 26-09-2005
Messages : 7 035

Re : (Python) jeux de lettres.

Re-

  Et alors, c'est raisonnable d'essayer ton programme jusque des mots de combien de lettres???

Fred.

Hors ligne

#5 09-11-2011 21:40:02

tibo
Membre expert
Inscription : 23-01-2008
Messages : 1 097

Re : (Python) jeux de lettres.

re,

sur mon vieux petit pc portable tout pouri , il lui faut 1 à 2mn pour 5 lettres, 5mn pour 6 lettres, au delà il refuse d'aller jusqu'au bout et arrete le processus, surement à cause du manque de mémoire.
Autant dire que pour le MEDITERRANEE de neroson, faut pas rever

Des que je peux, j'essaye sur un vrai ordi

Dernière modification par tibo (09-11-2011 21:44:18)


A quoi sert une hyperbole?
----- A boire de l'hypersoupe pardi !

Hors ligne

#6 10-11-2011 23:35:09

tibo
Membre expert
Inscription : 23-01-2008
Messages : 1 097

Re : (Python) jeux de lettres.

Bon, même sur un pc plus performant, Python me revoit l'erreur
"out of memory"

je vais essayer de l’alléger un peu, mais j'ai du mal a voir coment.


A quoi sert une hyperbole?
----- A boire de l'hypersoupe pardi !

Hors ligne

#7 12-11-2011 20:43:10

tibo
Membre expert
Inscription : 23-01-2008
Messages : 1 097

Re : (Python) jeux de lettres.

Re,

J'ai fait une erreur (que Karlun a faite aussi) dans mon premier script:
chercher les anagrammes  d'un mots c'est faire des permutations sans répétiton des lettres du mot.
Par exemple 'emeemnnan' n'est pas un anagramme de 'allemagne', et pourtant Karlun obtient cel anagramme dans sa liste.
Du coup au lieu d'avoir des listes de n^n éléments, ça ne fait "plus que" n! éléments.

Mais j'ai un problème du coup, je ne sais pas comment obtenir toutes les permutations d'un liste.
J'y avais déjà réfléchi pour un autre programme, et ce fut un echec.
Alors je connais pas mal de truc sur le groupe des permutations Sn mais visiblement pas assez pour le programmer.
J'avais notamment essayer d'utiliser que Sn est engendré par les 2-cycles, mais sans résultat probant.
Je vais ouvrir une autre discussion à ce sujet, au cas ou quelqu'un aurait des idées.

J'ai trouvé la bibliothèque itertools qui possède plusieurs fonctions sympathiques de permutation et de combinaison entre autre.Mais le problème de mémoire n'est toujours pas résolu ; j'ai toujours des listes gigantesques.
Alors n! c'est beaucoup plus petit que n^n, donc maintenant mon programme fonctionne raisonnablement jusqu'à 7 lettres, 8 ça devient long, 9 on en parle même pas.

A suivre...


A quoi sert une hyperbole?
----- A boire de l'hypersoupe pardi !

Hors ligne

#8 12-11-2011 20:58:42

karlun
Membre
Inscription : 05-05-2010
Messages : 216

Re : (Python) jeux de lettres.

Bonsoir,

"...sans répétiton des lettres du mot"
"Par exemple 'emeemnnan' n'est pas un anagramme de 'allemagne', et pourtant Karlun obtient cel anagramme dans sa liste."

Euh? j'sais pas!
Pas logiquement entrevu.
Je demande ......     à apprendre.

A+-*/

Dernière modification par karlun (12-11-2011 21:18:50)


Qui trouve, cherche.

Hors ligne

Réponse rapide

Veuillez composer votre message et l'envoyer
Nom (obligatoire)

E-mail (obligatoire)

Message (obligatoire)

Programme anti-spam : Afin de lutter contre le spam, nous vous demandons de bien vouloir répondre à la question suivante. Après inscription sur le site, vous n'aurez plus à répondre à ces questions.

Quel est le résultat de l'opération suivante (donner le résultat en chiffres)?
un plus sept
Système anti-bot

Faites glisser le curseur de gauche à droite pour activer le bouton de confirmation.

Attention : Vous devez activer Javascript dans votre navigateur pour utiliser le système anti-bot.

Pied de page des forums