Recherche d'une liste imbriquée arbitrairement et en retournant le chemin (Python)

Question

donc x est la valeur que je suis à la recherche dans la liste imbriquée t. Je comprends ce qui se passe à travers le code et la compréhension de la liste, ce que je ne comprends pas est à quel point [5] devient path, alors [3,5] devient path et enfin [1,3,5] est retourné pour montrer le chemin final des valeurs.

def findPath(t, x): 
    if t[0] == x: 
     return [t[0]] 
    for path in [findPath(branch, x) for branch in t[1:]]: 
     if path: 
      return [t[0]] + path 

t = [1, [3, [4], [5]], [2]] 

findPath(t, 5) 
#returns [1,3,5] 
findPath(t, 2) 
#returns [1 ,2] 

Voici un lien qui m'a aidé à comprendre pas à pas, je ne comprends pas comment la liste devient le chemin finalement retour [t [0]] + chemin. https: // goo.gl/ZRrZv7

Answer 1

Imaginez t être une structure arborescente, comme ceci:

[1, [3, [4], [5]], [2]] 

      || 

       1 
      / \ 
      3  2 
     /\ 
     4 5 

Vous continuez à parcourir l'arbre, explorant chaque chemin. Les impasses retournent None, donc if path est False pour les impasses. Lorsque vous trouvez le chemin que vous recherchez (exemple, 5), [5] est renvoyé. path n'est pas None, donc if path est True, donc vous renvoyez t[0] + [5] = [3, 5]. De même, dans le niveau au-dessus, [3, 5] n'est pas None, vous revenez t[0] + [3, 5] = [1, 3, 5]. Si aucun chemin n'est trouvé, alors rien n'est retourné nulle part (seulement None est retourné, pour être exact).

Le même raisonnement suit pour votre deuxième exemple.

Answer 2

Je ne suivais pas le lien parce que je ne suis généralement pas des liens qui ne sont pas pour les sites Web couramment utilisés, mais est ici une explication de ce qui se passe:

t = [1, [3, [4], [5]], [2]] 

Au niveau de la pile (0) nous appel:

findPath(t, 5) 

Cette évalue à:

findPath([1, [3, [4], [5]], [2]], 5) 

Nous sta rt niveau de pile (0) en vérifiant t[0]. Nous allons le représenter avec la notation List (<stack level>: <current index>), ce qui nous donne ici (0: 0).

À ce stade, t[0] n'est pas égal à , donc nous passons par la condition else non spécifiée de l'instruction if et passons à l'itération suivante de la boucle for.Nous incrémente l'indice du niveau de la pile actuelle (0: 1) et ajouter un autre niveau de la pile (1), ce qui nous donne un état de (0: 1, 1: 0), où nous appelons:

findPath([3, [4], [5]], 5) 

Encore une fois, t [0] est pas égal à x, donc on incrémente l'indice du niveau de pile courant (0: 1, 1: 1) et ajouter un autre niveau de pile pour essayer (0: 1, 1: 1, 2: 0), qui nous fait appeler:

findPath([4], 5) 

ici t[0] n'est pas égal à x et t[1:] est vide, donc nous redescendons le niveau de la pile pour empiler le niveau (1) et reprenons là où nous nous étions arrêtés; nous incrémentons le compteur à ce niveau à (0: 1, 1: 2) puis ajoutons un niveau de pile, ce qui nous donne (0: 1, 1: 2, 2: 0). Cela nous appelle: findPath ([5], 5)

Aha! Maintenant, t[0] est égal à x au niveau de pile le plus élevé, donc nous construisons [t[0]]; cela évalue à [5]. Ensuite, nous redescendons au niveau de la pile et reprenons là où nous nous étions arrêtés; nous étions à (0: 1, 1: 2). Maintenant, findPath a renvoyé une valeur de sorte que nous sommes dans la condition if pour la première fois au lieu de passer à l'itération suivante. Nous prenons donc t[0] au niveau de la pile actuelle et y ajoutons la valeur de retour; ceci évalue à ajouter [5] à [3], ce qui nous donne [3,5].

Ensuite, nous redescendons à (0: 1) et répétons le processus; maintenant nous devons ajouter [3,5] à [1], donc nous obtenons [1,3,5].

Est-ce que cela commence à avoir du sens? J'ai fait une notation bizarre ici parce que je ne veux pas passer du temps à dessiner des images, mais pour vraiment comprendre cela, vous devriez dessiner les niveaux de pile pour vous-même.