On Ricerca della profondità massima di un elenco annidato arbitrariamente

Question

Attualmente sto lavorando con una funzione ricorsiva in Python, e ho incontrato un muro. Come indicato, il problema è di restituire la profondità massima di una lista annidata arbitrariamente.

Ecco quello che ho finora:

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 

ho la sensazione che il problema è con i miei chiamate ricorsive (puo 'essere ovvio). In effetti restituirà var quando l'elenco è arrivato alla fine, ma quando ho un elenco non vuoto, le cose vanno male. Nulla viene restituito affatto.

Sto tagliando sbagliato? Dovrei fare qualcosa prima della fetta nella chiamata ricorsiva?

Il problema potrebbe riguardare anche il caso base.

Answer 1

Quindi, in sostanza, la struttura dati a cui si fa riferimento è un albero k-ary, noto anche come albero n-ary, con una ramificazione arbitraria. Ecco il codice per determinare il max. profondità di un albero n-ari con ramificazione arbitraria.

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 

È possibile visualizzare il codice in azione con diversi ingressi di prova here.

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.

Ecco perché non hai return economico, fatta eccezione nel caso else base per una lista vuota. E se cadi dalla fine della funzione senza colpire un return, significa che la funzione restituisce None.

Ma hai anche un altro problema. Stai iniziando con lo var = 0, quindi probabilmente con lo var += 1 ... ma non lo stai passando alle chiamate ricorsive o utilizzando i risultati delle chiamate ricorsive. Quindi le chiamate ricorsive non hanno alcun effetto utile.

Ciò che probabilmente si intende è qualcosa di simile:

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 

Ma questo ancora non è in realtà a destra. Il conteggio della profondità di una lista è 1 più del conteggio della profondità del suo elemento più profondo. Basta controllare il suo elemento secondo non ti servirà a nulla; è necessario controllare tutti di loro. Allora, che cosa si vuole veramente è qualcosa di simile:

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 

---

Se si desidera sostituire quella iterativa for x in lst con un secondo strato di ricorsione , naturalmente è possibile, ma non riesco a vedere alcun buon motivo per farlo; rende il codice più complicato senza motivo. Per esempio:

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 

---

Questo può ancora non essere di destra. Fa sicuramente la cosa giusta per, ad es., [1, [2,3], [4, [5]]]. Ma cosa dovrebbe fare per, per esempio, []? Non posso dire dalla tua domanda. Se dovesse restituire 0 o 1, sarà ovviamente necessario modificare lo if in modo appropriato. Se questo è un input illegale, allora sta già facendo la cosa giusta.(E che dovrebbe rispondere anche alla domanda su cosa si dovrebbe fare per, ad esempio, [[[], []], [], [[]]], ma assicurarsi che si pensa attraverso questo caso pure.)

Answer 3

se sono solo annidati liste, ad esempio, [[[], []], [], [[]]], ecco una bella soluzione:

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

Ecco una leggera variazione si può usare se non si utilizza Python 3.4, in cui è stato introdotto l'argomento default:

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

Si differenziano anche per il modo in cui contano. Il primo considera la lista vuota come profondità 1, la seconda come profondità 0. La prima è facile da adattare, però, basta fare il default -1.

---

Se non sono solo annidati liste, per esempio, [[[1], 'a', [-5.5]], [(6,3)], [['hi']]]), qui ci sono adattamenti a che:

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)) 

assicurarsi di aver compreso come funziona il secondo uno. Se non lo conoscete ancora, ti insegnerà come and opere in Python :-)

---

Prendendo il "puramente ricorsivo" sfida:

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)) 

scontato, l'extra l'argomento è leggermente brutto, ma penso che sia ok.