Partage

[Python] recursivité

petite aide.

Le 4 décembre 2009 à 11:21:33

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 ^^
Publicité
Le 4 décembre 2009 à 11:21:33
Le 4 décembre 2009 à 12:49:33

Merci pour votre aide malgré que ce n'est pas récursif.
Que fais defaultDict et random.choices ? Cela pourrai m'être utile par la suite.
anonyme
Photo
Le 4 décembre 2009 à 19:31:53

Tu sais que tu as une commande help ?

Tu peux peut-être l'utiliser un peu tu crois pas?

Le 5 décembre 2009 à 1:32:15

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:

mots = defaultdict(list)
anonyme
Photo
Le 5 décembre 2009 à 9:46:17

>>> a=defaultdict(list)
>>> print a
defaultdict(<type 'list'>, {})
>>> a.values()
[]
>>> a[0]="bonjour"
>>> print a
defaultdict(<type 'list'>, {0: 'bonjour'})
>>> print a.values()
['bonjour']
>>> a.pop(0)
'bonjour'
>>> print a
defaultdict(<type 'list'>, {})
>>> a[0].append(3)
>>> print a
defaultdict(<type 'list'>, {0: [3]})
>>> a[1].append("coucou")
>>> print a
defaultdict(<type 'list'>, {0: [3], 1: ['coucou']})


Le 5 décembre 2009 à 9:59:12

Citation : fla08

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 ...
Le 5 décembre 2009 à 10:47:42

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.
Le 6 décembre 2009 à 11:51:45

oops, pitite erreur dans mon code, corrigée
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)
Le 6 décembre 2009 à 11:55:03

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).
anonyme
Photo
Le 6 décembre 2009 à 13:17:34

C'est clair que ce code est affreux, et ne motivera sûrement pas un débutant à se mettre sous python.

:p
Le 6 décembre 2009 à 21:59:13

Citation : bluestorm

... 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.
Le 6 décembre 2009 à 22:07:36

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.
Le 6 décembre 2009 à 22:16:21

Citation : bluestorm

un dictionnaire indexé par les préfixes qui nous intéressent


ha ouéééé, ça c'est intelligent ... ça m'énerve de ne pas y avoir pensé moi-même. :colere:
je m'y mets desuite.
Le 6 décembre 2009 à 22:20:42

Oui, enfin tu pourrais aussi lire le code que j'ai posté quelques messages plus haut.
Le 6 décembre 2009 à 23:00:33

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.
Le 6 décembre 2009 à 23:19:29

Un petite condition et le tour est joué je suppose
Le 6 décembre 2009 à 23:59:02

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.
Le 7 décembre 2009 à 9:08:54

Citation

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.
Le 7 décembre 2009 à 9:55:46

Une ligne de 150 caractères, c'est pas ce que j'appelle quelque chose de "compact", c'est juste chiant.

80 caractères maxi, surtout si ton code doit être lu par d'autres ;)
Blond, bouclé, toujours le sourire aux lèvres...
Le 7 décembre 2009 à 10:12:57

Citation

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.

[Python] recursivité

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