Forum de mathématiques - Bibm@th.net
Vous n'êtes pas identifié(e).
- Contributions : Récentes | Sans réponse
Pages : 1
#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):
#-*- 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:
['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 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
#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
Pages : 1