pourquoi faire simple ... ?
et puis, si son prof voit ça, il va pitêtre se douter que c'est pas fla08 qui a pondu le code, donc c'est pas comme si je lui avais fait son devoir
Oui oui c'est ce que j'ai fais mais parfois une aide supplémentaire et qui plus est en francais est toujours la bienvenue. Et personnelement je ne comprend pas grand chose à defaultdict à part le fait qu'il s'agit d'un groupe de fonction sur les dictionnaires.
Par exemple je ne comprend pas cette ligne:
Merci pour votre aide malgré que ce n'est pas récursif...
faire une fonction recursive n'est utile que s'il y a une inconnue; par exemple faire une recherche dans une liste de listes dont on ne connait pas de niveau d'imbrication.
dans ton exo, il n'y a pas d'inconnu.
peut-être; s'il fallait trouver la chaine la plus longue ...
Effectivement, si on voulait faire du backtracking au lieu d'échouer en cas d'erreur, une fonction récursive simplifierait les choses (même si on peut s'en sortir autrement). Malheureusement, l'implémentation de Python supporte mal les fonctions récursives, et ça ne permettrait donc pas de générer des chaînes très longues.
def chaine(filename,n,c):
mots = [mot.strip() for mot in open(filename).readlines() if len(mot) >= c+2] #c+1 ne prennait pas en compte le \n"
soluces = [[random.choice(mots)]]
print "recherche pour",soluces[0][0]
try :
for i in range(n) : soluces = [[soluce+[mot] for mot in mots if mot not in soluce and mot[:c] == soluce[-1][-c:]] for soluce in soluces if len(soluce) > i][0]
except :
print "il n'y a pas de solution "
return
for mot in random.choice(soluces)[:-1] : print mot
import random
chaine(mon_fichier,14,2)
Mais ce code n'est pas lisible (trois for et deux if sur une seule ligne, elle est où la restriction des 80 colonnes ?) et n'est pas efficace (recherche linéaire dans le dictionnaire à chaque étape).
... et n'est pas efficace (recherche linéaire dans le dictionnaire à chaque étape).
oué, là j'avoue que c'est nul ... mais c'est parce que je voulais pouvoir sortir toutes les soluces avant d'en prendre une au hasard, suffit de modifier la fin du code pour toutes les afficher.
Non, ce n'est pas cette partie là qui pose problème (enfin elle est aussi mauvaise d'un point de vue algorithmique, mais ce n'est pas cela que je parlais), c'est la partie où tu choisis le prochain mot dans une solution : tu parcours ta base de mot en entier en filtrant ceux qui commencent convenablement, pour choisir le prochain mot.
Pour éviter ça, il suffit d'utiliser une structure de donnée adaptée, comme je l'ai fait dans mon code (un dictionnaire indexé par les préfixes qui nous intéressent). Pour des applications plus poussées, un arbre lexical (ou trie) serait encore préférable.
juste un truc dans ton code: ça ne teste pas si le mot tiré est déjà présent dans chaine, ainsi si foo.txt contient 'aaaaa' on peut se retrouver avec ['aaaaa','aaaaa''aaaaa','aaaaa',...] en sortie.
Tout à fait (j'ai juste écrit mon code pour donner des idées, on peut l'améliorer de multiples façon).
Pour que ce soit efficace si on veut de longues chaînes de mots, on peut même utiliser des structures de données qui permettent de tester l'appartenance plus facilement (set, mais il faut conserver la liste à côté pour avoir l'ordre des éléments), mais je pense que dans un premier temps une implémentation satisfaisante du backtracking (retour en arrière si la chaîne choisie ne permet pas d'obtenir une solution) serait une direction plus intéressante. Pour ce genre de choses, la récursion facilite beaucoup la tâche.
Pour ce genre de choses, la récursion facilite beaucoup la tâche.
ou un filtre... oui je sais, mais j'aime bien les mutations de liste
voilà mon code en intégrant la structure donnée par bluestorm, je ne connaissait pas, c'est bien pratique.
import random
from collections import defaultdict
def chaine(filename,n,c):
choix = defaultdict(list)
[choix[mot[:c]].append(mot.strip()) for mot in open(filename).readlines() if len(mot) >= c+2]
soluces = [[random.choice(random.choice(choix.values()))]]
print "recherche pour",soluces[0][0]
try :
for i in range(n-1) : soluces = [[soluce+[mot] for mot in choix[soluce[-1][-c:]] if mot not in soluce] for soluce in soluces if len(soluce) > i][0]
if soluces :
print random.choice(soluces)
return
except : pass
print "il n'y a pas de solution "
chaine('foo.txt',6,2)
pour ce qui est de la beauté de mon code, certains diront que je ferai mieu de faire du perl ^^; mais c'est mon style...compact.
désolé de pourrir le thread je sors.
ou un filtre... oui je sais, mais j'aime bien les mutations de liste
Sauf qu'avec ta liste tu calcules l'ensemble des solutions, donc toutes les solutions en même temps, ce qui est beaucoup plus lent, lourd et inutile (si on ne le demande pas) que le calcul d'une seule solution qui convient, en utilisant du backtracking en cas d'erreur.
Tu serais pas du genre un peu obstiné ?
LoupSolitaire +1 : ce n'est pas compact, c'est juste difficile à lire.
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
Python c'est bon, mangez-en.
Python c'est bon, mangez-en.
Python c'est bon, mangez-en.
Python c'est bon, mangez-en.
Python c'est bon, mangez-en.
Python c'est bon, mangez-en.
Python c'est bon, mangez-en.
Blond, bouclé, toujours le sourire aux lèvres...