Ein Auffinden der maximalen Tiefe einer beliebig verschachtelten Liste

Question

Ich arbeite derzeit mit einer rekursiven Funktion in Python, und ich habe in eine Wand gerannt. Wie angegeben, besteht das Problem darin, die maximale Tiefe einer beliebig verschachtelten Liste zurückzugeben. Hier

ist das, was ich bisher:

def depthCount(lst): 
    'takes an arbitrarily nested list as a parameter and returns the maximum depth to which the list has nested sub-lists.' 

    var = 0 

    if len(lst) > 0: 

     if type(lst[0]) == list: 
      var += 1 
      depthCount(lst[1:]) 

     else: 
      depthCount(lst[1:]) 

    else: 
     return var 

Ich glaube, dass das Problem mit meinem rekursiven Aufruf ist (dies kann offensichtlich sein). Es wird tatsächlich var zurückgeben, wenn die Liste das Ende erreicht hat, aber wenn ich eine nicht leere Liste habe, gehen die Dinge schief. Nichts wird zurückgegeben.

Bin ich falsch schneiden? Sollte ich im rekursiven Call etwas vor dem Slice machen?

Das Problem kann auch mit meinem Basisfall sein.

Answer 1

Also, im Wesentlichen ist die Datenstruktur, auf die Sie sich beziehen, ein k-ary Baum, auch als n-ary Baum bekannt, mit beliebigen Verzweigungen. Hier ist der Code zur Bestimmung der max. Tiefe eines n-ären Baumes mit beliebiger Verzweigung.

def maxdepth(tree): 
    if isleaf(tree): 
     return 1 
    maximum = 0 
    for child in children(tree): 
     depth = maxdepth(child) 
     if depth > maximum: 
      maximum = depth 
    return maximum + 1 

Sie können here den Code in Aktion mit verschiedenen Testeingaben sehen.

Answer 2

It will indeed return var when the list has reached the end, but when I have a nonempty list, things go awry. Nothing is returned at all.

Das ist, weil Sie keine return Erklärung haben, außer im else Basisfall für eine leere Liste. Und wenn Sie vom Ende der Funktion fallen, ohne eine return zu treffen, bedeutet dies, dass die Funktion None zurückgibt.

Aber Sie haben noch ein weiteres Problem. Du startest var = 0, dann möglicherweise var += 1 ... aber du gibst das nicht in die rekursiven Aufrufe weiter, oder benutze irgendein Ergebnis der rekursiven Aufrufe. Daher haben die rekursiven Aufrufe überhaupt keinen nützlichen Effekt.

Was Sie wahrscheinlich so etwas wie das gemeint ist:

def depthCount(lst): 
    'takes an arbitrarily nested list as a parameter and returns the maximum depth to which the list has nested sub-lists.' 

    if len(lst) > 0: 

     if type(lst[0]) == list: 
      return 1 + depthCount(lst[1:]) 
     else: 
      return depthCount(lst[1:]) 

    else: 
     return 0 

Aber das ist noch nicht wirklich richtig. Die Tiefenzählung einer Liste ist 1 mehr als die Tiefenanzahl ihres tiefsten Elements. Nur seine Sekunde Element überprüfen tut dir nicht gut; Sie müssen alle von ihnen überprüfen. Also, was Sie wirklich wollen, ist so etwas wie dieses:

def depthCount(lst): 
    'takes an arbitrarily nested list as a parameter and returns the maximum depth to which the list has nested sub-lists.' 
    if isinstance(lst, list): 
     return 1 + max(depthCount(x) for x in lst) 
    else: 
     return 0 

---

Wenn Sie diese iterative for x in lst mit einer Sekunden Schicht Rekursion ersetzen wollen, natürlich können Sie, aber ich kann noch nichts sehen guter Grund, dies zu tun; Es macht den Code ohne Grund komplizierter. Zum Beispiel:

def max_child_count(lst): 
    if lst: 
     return max(depth_count(lst[0]), max_child_count(lst[1:])) 
    else: 
     return 0 

def depth_count(lst): 
    if isinstance(lst, list): 
     return 1 + max_child_count(lst) 
    else: 
     return 0 

---

Diese kann noch nicht richtig sein. Es tut definitiv das Richtige für z. B. [1, [2,3], [4, [5]]]. Aber was sollte es für sagen, []? Ich kann es von deiner Frage nicht sagen. Wenn es 0 oder 1 zurückgibt, müssen Sie natürlich die if entsprechend ändern. Wenn das illegale Eingabe ist, dann macht es schon das Richtige.(Und die sollte beantworten auch die Frage, was es für tun sollte, zum Beispiel [[[], []], [], [[]]], aber stellen Sie sicher, dass Sie auch diesen Fall durchdenken.)

Answer 3

Wenn sie Listen nur verschachtelt, zB [[[], []], [], [[]]], hier ist eine schöne Lösung:

def depthCount(lst): 
    return 1 + max(map(depthCount, lst), default=0) 

hier ist eine leichte Variation Sie, wenn Sie Python 3.4 nicht verwenden, verwenden könnte, wo das default Argument eingeführt:

def depthCount(lst): 
    return len(lst) and 1 + max(map(depthCount, lst)) 

Sie unterscheiden sich auch dadurch, wie sie zählen. Die erste betrachtet die leere Liste als Tiefe 1, die zweite als Tiefe 0. Die erste ist leicht anzupassen, obwohl sie nur den Standardwert -1 hat.

---

Wenn sie nicht nur Listen verschachtelt, zum Beispiel [[[1], 'a', [-5.5]], [(6,3)], [['hi']]]), hier sind Anpassungen an, dass:

def depthCount(x): 
    return 1 + max(map(depthCount, x)) if x and isinstance(x, list) else 0 

def depthCount(x): 
    return int(isinstance(x, list)) and len(x) and 1 + max(map(depthCount, x)) 

Stellen Sie sicher, Sie verstehen, wie die letztere funktioniert. Wenn Sie es noch nicht kennen, wird es Ihnen beibringen, wie and Werke in Python :-)

---

Unter der "rein rekursive" Herausforderung:

def depthCount(x, depth=0): 
    if not x or not isinstance(x, list): 
     return depth 
    return max(depthCount(x[0], depth+1), 
       depthCount(x[1:], depth)) 

Zugegeben, die extra Argument ist etwas hässlich, aber ich denke, es ist in Ordnung.