Durchsuchen einer beliebig verschachtelten Liste und Zurückgeben des Pfads (Python)

Question

Also x ist der Wert, den ich in der verschachtelten Liste t suche. Ich verstehe, was im Code und im Listenverständnis passiert, was ich nicht verstehe ist, an welchem ​​Punkt [5] Pfad wird, dann wird [3,5] Pfad und schließlich [1,3,5] kehrt zurück, um das zu zeigen endgültiger Pfad der Werte.

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] 

Hier ist ein Link, den ich Schritt für Schritt verstehen geholfen, ich verstehe einfach nicht, wie die Liste der Pfad Pfad schließlich Rückkehr [t [0]] + wird. https: // goo.gl/ZRrZv7

Answer 1

t Stellen Sie sich eine Baumstruktur, so zu sein:

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

      || 

       1 
      / \ 
      3  2 
     /\ 
     4 5 

Sie halten überquert den Baum, jeden Weg zu erkunden. Sackgassen kehren zurück None, so if path ist False für Sackgassen. Wenn Sie den gewünschten Pfad gefunden haben (Beispiel 5), wird [5] zurückgegeben. path ist nicht None, also if path ist True, so dass Sie t[0] + [5] = [3, 5] zurückgeben. Ähnlich ist [3, 5] in der obigen Ebene nicht None, daher geben Sie t[0] + [3, 5] = [1, 3, 5] zurück. Wenn kein Pfad gefunden wird, wird nichts zurückgegeben (nur None wird zurückgegeben, um genau zu sein).

Die gleiche Argumentation folgt für Ihr zweites Beispiel.

Answer 2

Ich habe nicht den Link folgen, weil ich nicht generell Links folgen, die nicht für häufig verwendete Websites sind, aber hier ist eine Erklärung, was passiert:

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

Bei Stack-Ebene (0) wir rufen:

findPath(t, 5) 

Dies ausgewertet:

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

Wir sta rt Stapelebene (0) durch Überprüfung t[0]. Wir werden dies mit der Notation List (<stack level>: <current index>) darstellen, die uns hier angibt (0: 0).

An diesem Punkt ist t[0] nicht gleich x, daher fallen wir durch die nicht angegebene else-Bedingung der if-Anweisung und gehen zur nächsten Iteration der for-Schleife über.Wir erhöhen den Index im aktuellen Stack-Ebene (0: 1) und einen anderen Stack-Ebene hinzufügen (1), die uns einen Zustand gibt (0: 1, 1: 0), wo wir nennen:

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

Wieder t [0] nicht gleich x ist, so erhöhen wir den Index im aktuellen Stack-Ebene (0: 1, 1: 1) und einen anderen Stack-Ebene hinzufügen, um zu versuchen (0: 1, 1: 1, 2: 0) das macht rufen Sie uns an:

findPath([4], 5) 

Hier t[0] ist nicht gleich x und t[1:] ist leer, also gehen wir wieder einen Stack-Level auf Stack-Level (1) und holen dort weiter, wo wir aufgehört haben; Wir erhöhen den Zähler auf dieser Ebene auf (0: 1, 1: 2) und fügen dann eine Stapelebene hinzu, die uns (0: 1, 1: 2, 2: 0) angibt. Das ruft uns an: findPath ([5], 5)

Aha! Jetzt ist t[0] gleich x auf der höchsten Stack-Ebene, also konstruieren wir [t[0]]; Dies ergibt [5]. Dann gehen wir wieder einen Stapel hinunter und holen dort ab, wo wir aufgehört haben; Wir waren um (0: 1, 1: 2). Jetzt hat findPath einen Wert zurückgegeben, so dass wir uns zum ersten Mal in der if-Bedingung befinden, anstatt zur nächsten Iteration überzugehen. Also nehmen wir t[0] auf der aktuellen Stack-Ebene und hängen den Rückgabewert an sie an; dies ergibt das Hinzufügen von [5] zu [3], was uns [3,5] gibt.

Als nächstes fallen wir wieder runter auf (0: 1) und wiederholen den Vorgang; Jetzt müssen wir [3,5] an [1] anhängen, so erhalten wir [1,3,5].

Ist das sinnvoll? Ich habe hier eine merkwürdige Notation gemacht, weil ich keine Zeit damit verbringen will, Bilder zu zeichnen, aber um das wirklich zu verstehen, sollten Sie die Stacklevel selbst herausziehen.