Discussion :

[simnitch]

Bonjour,

j'ai codé le code qui suit pour faire une recherche dans un arbre bianire qui n'est pas triée, mais j'ai été obligé d'utiliser une variable globale extérieure à la fonction pour enregistrer les résultats des chemins qui mènent à la valeur de feuille recherchée (il peut y avoir plusieurs fois la valeur recherchée). Voyez-vous un moyen de faire pour avoir ce résultat retournée par la fonction (et None s'il n'y en pas).

Voici ce que j'ai fait :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
# -*- coding: utf-8 -*-
 
arbre = ['+', ['+', ['*', 4, ['*', 4, 2]], 2], ['*', ['*', 4, 2], 2]]# 
 
def arbre_gauche(arbre) :
    return arbre[1]
 
def arbre_droit(arbre) :
    return arbre[2]
 
def est_vide(arbre) :
    if arbre == [] : #???
        return True
    else :
        return False
 
#print arbre_gauche(arbre)
 
 
Res = []
 
#retourne le chemin pour mener à la feuille si elle a été trouvée,False sinon
def recherche(feuille, arbre, chemin = []) :
    global Res
    if est_vide(arbre) :
        return 
    if isinstance(arbre_gauche(arbre), list) :
        recherche(feuille, arbre_gauche(arbre), chemin + [1])
    if isinstance(arbre_droit(arbre), list) :
        recherche(feuille, arbre_droit(arbre), chemin + [2])  
    if arbre_gauche(arbre) == feuille :
        chemin += [1]
        Res += [chemin]
        return 
    if arbre_droit(arbre) == feuille :
        chemin += [2]
        Res += [chemin]
        return
 
 
recherche(12, arbre)
print Res

Merci d'avance pour vos réponses!

[VinsS]

Salut,

Ce n'est pas une question de global, ton code ne peut pas aboutir.

Les deux conditions qui peuvent modifier Res sont:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
    if arbre_gauche(arbre) == feuille :
        ... 
    if arbre_droit(arbre) == feuille :

feuille vaut 12 et ne varie jamais et, ni arbre_gauche, ni arbre_droit ne peuvent retourner 12.

Conclusion, Res reste []

[simnitch]

Salut et merci de ta réponse. Mon code marche, là en effet res vaudra [] mais si j'exécute recherche(2, arbre) j'aurais les bons résultats dans res. Mon problème est de coder ceci plus joliment, et de façon à pouvoir utiliser if recherche(2, arbre) == None : plutôt que de faire recherche(2, arbre) et tester si Res == None.
A la limite si ce n'est pas possible en renvoyant toutes les solutions, en renvoyer une seule m'irait, mais je ne sais pas comment sortir de la fonction et arreter les autres appels récursifs si une solution a été trouvé (sans utiliser la fonction exit() ).

[VinsS]

Tu peux passer la liste en argument, c'est pareil.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
 
# -*- coding: utf-8 -*-
 
arbre = ['+', ['+', ['*', 4, ['*', 4, 2]], 2], ['*', ['*', 4, 2], 2]]
 
def arbre_gauche(arbre) :
    print 'gauche:', arbre[1]
    return arbre[1]
 
def arbre_droit(arbre) :
    print 'droit:', arbre[2]
    return arbre[2]
 
def est_vide(arbre) :
    if arbre == [] : # if not arbre:
        return True
    else :
        return False
 
#retourne le chemin pour mener à la feuille si elle a été trouvée,False sinon
def recherche(feuille, arbre, Res, chemin = []) :
 
    if est_vide(arbre) :
        return
    if isinstance(arbre_gauche(arbre), list) :
        recherche(feuille, arbre_gauche(arbre), Res, chemin + [1])
    if isinstance(arbre_droit(arbre), list) :
        recherche(feuille, arbre_droit(arbre), Res, chemin + [2])  
    if arbre_gauche(arbre) == feuille :
        chemin += [1]
        Res += [chemin]
        return Res
    if arbre_droit(arbre) == feuille :
        chemin += [2]
        Res += [chemin]
        return Res
    return Res
 
ch = recherche(2, arbre, [])
print ch

J'ai testé avec feuille = 2 les deux versions, j'ai le même résultat:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
[[1, 1, 2, 2], [1, 2], [2, 1, 2], [2, 2]]

[wiztricks]

Salut,

Salut et merci de ta réponse. Mon code marche, là en effet res vaudra [] mais si j'exécute recherche(2, arbre) j'aurais les bons résultats dans res. Mon problème est de coder ceci plus joliment, et de façon à pouvoir utiliser if recherche(2, arbre) == None : plutôt que de faire recherche(2, arbre) et tester si Res == None.

C'est une fonction récursive.
Plutôt que de trimbaler "chemin" en variable locale essayez de vous en débarrasser.
L'idée étant de remplacer des formes comme:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
    if isinstance(arbre_gauche(arbre), list) :
        recherche(feuille, arbre_gauche(arbre), chemin + [1])

par:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
    if isinstance(arbre_gauche(arbre), list) :
        return [1] + recherche(feuille, arbre_gauche(arbre))

i.e. on remplace la variable locale par le résultat d'un calcul "local".

- W

[davcha]

Dans le pire des cas, tu peux toujours faire ceci :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
def foo(params):
  buffer = []
  def bar(params):
     ...
     buffer = ....
     ...
  bar(params)
  return buffer

[simnitch]

Merci bien pour ta réponse wiztricks!
J'ai donc testé un truc comme ceci :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def recherche(feuille, arbre) :
    if est_vide(arbre) :
        return False
    if isinstance(arbre_gauche(arbre), list) :
        if recherche(feuille, arbre_gauche(arbre)) == False : return False
        return [1] + recherche(feuille, arbre_gauche(arbre))
    if isinstance(arbre_droit(arbre), list) :
        if recherche(feuille, arbre_droit(arbre)) == False : return False
        return [2] + recherche(feuille, arbre_droit(arbre))
    if arbre_gauche(arbre) == feuille :
        return [1]
    if arbre_droit(arbre) == feuille :
        return [2]
    return False

Mais j'ai deux problèmes, déjà je suis obligé (y'a sûrement une manière plus élégante de faire non?) de tester la valeur que retournera l'appel suivant pour ne pas avoir à concatener une liste et False. (Sinon il faudrait que je retourne [False] mais alors la fonction retournerait quand même une liste au lieu de False si elle n'a rien trouvée.) Autre gros problème, si la fonction arrive a un sous arbre dont les deux feuilles ne sont pas les feuilles recherchées, alors la fonction renvoie False et coupe les autres récursions, et je ne vois pas comment l'éviter.

[wiztricks]

Salut,

Ah oui c'est beurk...
On pourrait écrire un truc comme çà:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
LEFT = 1
RIGHT = 2
 
def recherche(feuille, arbre) :
 
    if len(arbre):
        for side in (LEFT, RIGHT):
            child = arbre[side]
            if isinstance(child, list):
                found = recherche(feuille, child)
                if found: 
                    return [side] + found
            if child == feuille:
                return [side]
    return []
 
print ('found', recherche(2, arbre))
print ('*found*', recherche(12, arbre))

Après le jeu serait de remplacer les "return" par "yield" pour récupérer tous les chemins.

- W

[Kurodiam]

@simnitch , vous avez utilisé trop de if , il serait de voir une suite de if et d'elif , et à la fin un else ( le return False se répète trop de fois , on dirait une condition générale , et il faudrait trier les conditions par ordre ) .C'est pour cette raison , qu'il y'a certaines conditions qui ne sont pas traitées par votre fonction .
Pourquoi voulez-vous créer des listes de feuilles ? Le plus souvent , c'est plutôt le langage lisp qui aborde ce genre de soucis ...

[simnitch]

wiztricks : merci beaucoup, c'est beaucoup plus élégant comme ça.

Kurodiam : c'est sûr qu'en lisp ce serait plus facile mais en lisp je sais faire, là j'essaie d'apprendre le python

Merci pour vos réponses

[wiztricks]

Juste pour le fun...
Avec des "yield", on peut récupérer les chemins et c'est une petite variation du code précédent:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
def search(leaf, tree):
    if not len(tree):
        return []
    for side in (LEFT, RIGHT):
        child = tree[side]
        if isinstance(child, list):
            for e in search(leaf, child):
                yield [side] + e
        if child == leaf:
            yield [side]
 
print ('***', list(search(2, arbre)))
print ('***',list(search(12, arbre)))

- W