Bonsoir,

J'ai un petit soucis avec une recurisité. Je voudrais que ma méthode récursive me retourne une liste de mot mais je n'arrive pas à générer la liste.
Voici mon code:

import random
def commence_par(fileName,seq):
    n = len(seq)
    liste = []
    fichier = open(fileName)
    for i in fichier:
        if i.strip()[0:n] == seq:
            liste.append(i.strip())
    return liste

def rec_suite(fileName, debut, n, c): #n est le nombre d'éléments au final dans la liste.
    tab = []
    if n == 0:
        return debut
    else:
        rand = commence_par(fileName, debut[-c:])
        i = random.randint(0,len(rand)-1)
        elem = rand[i]
        tab.append(rec_suite(fileName,elem,n-1,c))
    return tab

Merci d'avance pour votre aide.

message d'erreur?

Bah je veux juste savoir comment ajouter récursivement mes elements dans un tableau.
Oui j'ai des message d'erreur mais du au fait qu'il n'y a pas de mot commençant par seq. Mais ça je vais gérer les erreurs par après. Pour le moment je me retrouve au final avec:
[[[[[[[mot]]]]]]]

exemple quand il n'y pas d'erreur entre temps:

>>> rec_suite('words.txt','ahead',10,2)
admixture
recaning
ngwee
eellike
keen
enlightenments
tsadi
displace
cerias
assayers
[[[[[[[[[['assayers']]]]]]]]]]

for i in fichier

serait plutôt

for i in fichier.readlines():

Oui si on travail sur un fichier txt normal, mais ici je travail sur un fichier txt où chaque ligne ne contient qu'un seul mot.Il s'agit en fait des mots d'un dictionnaire anglais.

Tu déclare une nouvelle liste vide tab dans ta fonction récursive, c'est pas logique, il vient de là ton bug je pense.

Je trouve ton code pas clair du tout, si tu peux pas faire plus expressif, essaye de commenter un peu

import random
def commence_par(fileName,seq):
""" Cette fonction retourne une liste de mot commencant par seq et se trouvant dans le fichier fileName """
    n = len(seq)
    liste = []
    fichier = open(fileName)
    for i in fichier: #Pour chaque mot dans le fichier fileName
        if i.strip()[0:n] == seq: #Si le mot i commence par seq
            liste.append(i.strip()) #le placer dans la liste
    return liste

def rec_suite(fileName, debut, n, c):
""" Cette fonction récursive retourne une suite de  n mot commençant chacun par les c dernières lettres du mot précédent.
    Les mots proviennent du fichier fileName. 
    debut est le premier mot de la liste."""
    tab = []
    if n == 0:
        return debut
    else:
        rand = commence_par(fileName, debut[-c:]) #génére la liste des mots commençant par les c dernières lettre de debut.
        i = random.randint(0,len(rand)-1) 
        elem = rand[i] #En prendre un au hasard dans le tas
        tab.append(rec_suite(fileName,elem,n-1,c)) #L'ajouter à la liste finale.
    return tab

Et à la sortie je voudrais ceci:

>>> rec_suite(’words.txt’,'aahed', 3, 3)
[’aahed’, ’heddles’, ’lesbian’]
>>> rec_suite(’words.txt’,'aahed', 10, 3)
[’aahed’, ’heddles’, ’lesbians’, ’ansate’, ’atechnic’,’nice’, ’iceberg’, ’ergastic’, ’tical’, ’calabash’]
>>> rec_suite(’words.txt’,'abound', 10, 5)
[’abound’, ’bounder’, ’undercover’, ’covers’, ’oversales’,’saleswoman’, ’womanising’, ’isinglass’, ’glassblower’, ’lowercase’]

L'énoncé:

4 Suite de mots
Veuillez créer une fonction suite_de_mots qui prend 3 arguments :
– filename, le nom d’un fichier texte (contenant un mot par ligne, comme words.txt) ;
– n, la taille de la suite à générer ;
– c, la taille de la contrainte.
La fonction doit générer une suite de n mots tirés du fichier nommé filename en respectant les
contraintes suivantes :
1. les mots de la suite doivent au moins être de taille c+1.
2. si w1 et w2 sont deux mots consécutifs de la suite générée, alors les c derniers caractères du mot
w1 sont identiques aux c premiers caractères du mot w2.
La suite doit ensuite être affichée à l’écran.
Il est conseillé d’utiliser des fonctions intermédiaires comme, par exemple,
– commence_par(filename, s) qui retourne une liste de tous les mots commençant par s dans
filename ;
– rec_suite(filename, debut, n, c), fonction récursive qui prend en paramètre :
– filename, le nom du fichier texte qui contient les mots ;
– debut, le premier mot imposé de la suite ;
– n, la taille de la suite à générer ;
– c, la taille de la contrainte.
Cette fonction récursive retourne une suite de n mots (sous forme de liste) respectant les
contraintes exprimées plus haut, et dont le premier mot est debut.
Si une telle suite n’existe pas, la fonction doit lancer une exception appropriée (de votre choix).
Voici le comportement attendu :
>>> suite_de_mots(’words.txt’, 3, 3)
[’aahed’, ’heddles’, ’lesbian’]
>>> suite_de_mots(’words.txt’, 10, 3)
[’aahed’, ’heddles’, ’lesbians’, ’ansate’, ’atechnic’,
’nice’, ’iceberg’, ’ergastic’, ’tical’, ’calabash’]
>>> suite_de_mots(’words.txt’, 10, 5)
[’abound’, ’bounder’, ’undercover’, ’covers’, ’oversales’,
’saleswoman’, ’womanising’, ’isinglass’, ’glassblower’, ’lowercase’]
Dans les exemples donnés, vous aurez remarqué que le premier mot commence par a. Ceci est dû
au fait que les mots candidats à être choisis sont pris dans l’ordre dans le fichier. Il vous est demandé
d’améliorer votre programme (version 2) pour que l’ordre dans le fichier n’ait pas d’influence sur la
probabilité qu’un mot soit choisis pour être dans la liste. D’ailleurs, deux lancements successifs de la
fonction pourraient donner deux suites de mots différentes.



Personne ?

le même mot peut-il apparaitre plusieur fois dans la liste ?
faut-il lister toutes les possibilités ?
y a-t-il forcement une solution repondant aux contraintes ?

l'algo est assez simple s'il n'existe qu'une unique solution; sinon, ça risque d'être compliqué ...

d'ailleur tu devrais nous mettre un algo plutot que du code.

Non on liste une possibilité aléatoire. Si on n'est pas capable de généré une liste de taille n pour une contrainte de taille c alors on retourne un erreur, mais cela je m'en occuperai par après. Le plus important est que je puisse générer cette liste. EN fait la seule chose que je demande c'est: comment puis-je ajouter des valeurs à une liste récursivement.

avec la methode append() dans une boucle, non ?

Bah c'est récursif donc pas de boucle xS

Citation

– rec_suite(filename, debut, n, c), fonction récursive qui prend en paramètre :

c'est débile comme méthode à mon avis, je comprendrai si c'etait des listes imbriquées, mais là ça sert à rien.
je peux pas t'aider car je ne comprends pas l'interet de la recursivité dans cette exercice

Citation

Il est conseillé d’utiliser des fonctions intermédiaires

d'alleur c'est pas obligatoire.

je peux t'aider sur l'utilisation d'une boucle, qui semble lus appropriée.

fla8 : je t'ai donné une partie de la solution : tu crée une nouvelle liste à chaque appel de la fonction récursive, alors forcément au lieu d'avoir une liste avec n elements, tu te retrouve avec n listes de 1 élément.

Je dois concaténer toutes les listes ?

Citation : fla08

Je dois concaténer toutes les listes ?

Si tu as :
[[[foo]]], les concaténer ne donnera rien d'intéressant.

Le problème vient du fait que tu crée n listes alors qu'il ne t'en faut qu'une, alors la solution est évidente : crée une seule liste.

Justement comment faire puisqu'à chaque appel recursif elle sera réinitialisé.

Elle sera réinitialisée parce que tu as conçu ton code comme ça, mais tu peux faire autrement

EDIT : Essaye déjà de faire une fonction récursive, qui va créer une liste de n élements ([1, 1, 1] par exemple, peu importe), tu pourra rajouter les contraintes de ton exercice plus tard )

>< je suis une cruche de la récursivité. Vive les boucles xD

Citation : fla08

>< je suis une cruche de la récursivité.

Ça peut changer, et si tu veux devenir un développeur honorable, ça doit changer.

Voir mon edit du précédent post

EDIT : Poursuis le raisonnement, si ta fonction est exécutée n fois (le principe de la récursivité), toutes les instructions seront exécutées n fois. Il y a deux solutions pour faire une chose une seule fois : le faire hors de la fonction, ou utiliser une condition.

RE EDIT : Il y a autre chose qui est fondamental, si tu veux construire une liste de façon récursive, il faut pouvoir utiliser la même liste à chaque appel de fonction !

Puisque tu aime les boucles, la comparaison est simple, la fonction récursive est comme le corps d'une boucle.
Ici tu fais l'équivalent de :

for n in range(5):
    l = []
    l.append(n)

Je pense que tu vois tout de suite le problème non ?

Normalement on ferait plutôt :

l = []
for n in range(5):
    l.append(n)

Ah j'ai trouvé une solution.

def rec_suite(fileName, debut, n, c):
    if n == 0:
        return [debut]
    else:
        rand = commence_par(fileName, debut[-c:]) 
        i = random.randint(0,len(rand)-1) 
        elem = rand[i]
        res = [elem]+(rec_suite(fileName,elem,n-1,c))
    return res

J'ai encore un petit problème, le dernier élément apparait 2 fois ><

Edit:

Réglé:

def rec_suite(fileName, debut, n, c):
    if n == 1:
        return [debut]
    else:
        res = [debut]
        rand = commence_par(fileName, debut[-c:]) 
        i = random.randint(0,len(rand)-1) 
        elem = rand[i]
        res = res + (rec_suite(fileName,elem,n-1,c))
    return res

Si n==0 tu devrais effectivement renvoyer une liste vide (puisqu'il debut est déjà ajouté à la liste à l'appel précédent) =)

Il y aurait tout de même des façon plus joli de faire en Python, mais vous étudiez certainement plus l'algo que le Python.

Oui je pense que la récursivité dans ce cas ci est plus fait pour l'aspect algorithmique qu'autre chose

c'est bien compliqué pour un algo aussi simple ... :\

Si vous avez des améliorations à apporter dites le moi je suis preneur

en fait, la recursivité dans cet exercice n'a de sens que s'il faut rechercher toutes les solutions, là oui ça a un interet.

Tu connais les liste comprehension ?

Tout ceci :

def commence_par(fileName,seq):
    n = len(seq)
    liste = []
    fichier = open(fileName)
    for i in fichier:
        if i.strip()[0:n] == seq:
            liste.append(i.strip())
    return liste

rand = commence_par(fileName, debut[-c:])

Pourrait s'écrire :

rand = [ m.strip() for m in open(fileName) if m[0:c] == debut[-c:] ]

+ une petite boucle à la place de la récursion et le tout tient en une petite dizaine de lignes sympas =)

Citation

Tu connais les liste comprehension ?

j'allai justement le dire ... je deteste quand on me devance !!!

Oui j'ai déjà utilisé mais j'y avais pas pensé ...honte à moi.

un truc dans ce genre:
le try/except c'est pour me la péter

def chaine(filename,n,c):
	mots = [mot.strip() for mot in open(filename).readlines() if len(mot) >= c+1]
	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)

Citation

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]

Oh oui, voilà du code très clair, bravo !

import random
from collections import defaultdict

def mots(filename,c):
    mots = defaultdict(list)
    for mot in open(filename).readlines():
        mot = mot.strip()
        if len(mot) >= c+1:
            mots[mot[:c]].append(mot)
    return mots

def chaine(mots,c,n):
    mot = random.choice(random.choice(mots.values()))
    chaine = [mot]
    for i in range(n-1):
        candidats = mots[mot[-c:]]
        if candidats == []: raise KeyError, "pas de solution pour %s" % mot
        else:
            mot = random.choice(candidats)
            chaine.append(mot)
    return chaine

def test(filename, c, n):
    print chaine(mots(filename, c), c, n)

test("foo.txt", 3, 10)