Wyszukiwanie najdłuższej listy na liście w Pythonie

Question

Mam do wyboru najdłuższą listę list w Pythonie.

Na przykład:

longest([1,2,3]) zwraca 3

longest([[[1,2,3]]]) również zwraca 3 (lista wewnętrzna wynosi 3)

longest([[], [3,[4,5],[2,3,4,5,3,3], [7], 5, [1,2,3], [3,4]], [1,2,3,4,5]]) powraca 7 (lista [3,[4,5],[2,3,4,5,3,3], [7], 5, [1,2,3], [3,4]] zawiera 7 elementów)

chwili mam ten kod, ale nie daje rady z pierwszych dwóch przykładów.

def longest(list1): 
    longest_list = max(len(elem) for elem in list1) 
    return longest_list 

Może rekurencja pomoże? Dziękujemy!

Answer 1

Oto rekurencyjny rozwiązaniem dla każdej listy głębokość:

def longest(l): 
    if(not isinstance(l, list)): return(0) 
    return(max([len(l),] + [len(subl) for subl in l if isinstance(subl, list)] + 
     [longest(subl) for subl in l])) 

Answer 2

Python 3.3 wersja:

def lengths(x): 
    if isinstance(x,list): 
     yield len(x) 
     for y in x: 
      yield from lengths(y) 

Wykorzystanie:

>>> l = [[], [3,[4,5],[2,3,4,5,3,3], [7], 5, [1,2,3], [3,4]], [1,2,3,4,5]] 
>>> max(lengths(l)) 
7 

W python 2.6+ nie masz oświadczenie yield from (został wprowadzony w Pythonie 3.3), więc trzeba zmienić kod nieznacznie:

def lengths(x): 
    if isinstance(x,list): 
     yield len(x) 
     for y in x: 
      for z in lengths(y): 
       yield z 

Answer 3

Rzeczywiście, rekursja może rozwiązać ten problem.

def longest(lst): 
    if type(lst) is not list: 
     return 0 
    max = len(lst) 
    for i in lst: 
     max_i = longest(i) 
     if max_i > max: 
      max = max_i 
    return max 

Answer 4

Można to zrobić z rekursji:

def longest(list1) : 
    l = 0 
    if type(list1) is list : 
     l = len(list1) 
     if l > 0 : 
      l = max(l,max(longest(elem) for elem in list1)) 
    return l 

(online demo).

Kod najpierw sprawdza, czy mamy do czynienia z tym is list. Jeśli tak, najpierw bierzemy len z listy. Następnie wykonujemy rekurencyjne wywołanie na jego elementach. I obliczyć maksimum longest elementów. Jeśli maksimum jest większe niż sama długość. Zwracamy maksimum, w przeciwnym razie zwracamy długość.

Ponieważ longest pozycji, która nie jest listą, wynosi zero, rekurencja zostanie zatrzymana, a my otrzymamy odpowiedź na pojedyncze elementy, które będą używane w kroku indukcyjnym.

Answer 5

Kolejna funkcja rekurencyjna używając mapy:

def longest(a): 
    return max(len(a), *map(longest, a)) if isinstance(a, list) and a else 0 

---

In [2]: longest([1,2,3]) 
Out[2]: 3 

In [3]: longest([[[1,2,3]]]) 
Out[3]: 3 

In [4]: longest([[], [3,[4,5],[2,3,4,5,3,3], [7], 5, [1,2,3], [3,4]], [1,2,3,4,5]]) 
Out[4]: 7 

i iteracyjnie:

def longest(a): 
    mx = 0 
    stack = [a[:]] 
    while stack: 
     cur = stack.pop() 
     if isinstance(cur, list): 
      mx = max(mx, len(cur)) 
      stack += cur 
    return mx 

---

In [6]: longest([1,2,3]) 
Out[6]: 3 

In [7]: longest([[[1,2,3]]]) 
Out[7]: 3 

In [8]: longest([[], [3,[4,5],[2,3,4,5,3,3], [7], 5, [1,2,3], [3,4]], [1,2,3,4,5]]) 
Out[8]: 7