Глубина подсчета или самый глубокий уровень вложенного списка

17

A имеют реальную проблему (и головную боль) с назначением ...

Я участвую в вводном классе программирования, и мне нужно написать функцию, которая, учитывая список, вернет «максимальную» глубину, к которой она идет ... Например: [1,2,3] вернется 1, [1, [2,3]] вернет 2 ...

Я написал этот фрагмент кода (это лучшее, что я мог получить T_T)

def flat(l):
    count=0
    for item in l:
        if isinstance(item,list):
            count+= flat(item)
    return count+1

Однако он явно не работает так, как должен, потому что, если есть списки, которые не учитывают максимальную глубину, он все равно поднимает счетчик ...

Например: когда я использую функцию с [1,2, [3,4], 5, [6], 7], она должна возвращать 2, но возвращает 3 ...

Любые идеи или помощь будут очень благодарны ^^ спасибо много! Я боролся с этим уже несколько недель ...

    
задан dhcarmona 18.05.2011 в 04:01
источник

10 ответов

2

Ширина - сначала без рекурсии, а также работает с другими типами последовательностей:

from collections import Sequence
from itertools import chain, count

def depth(seq):
    for level in count():
        if not seq:
            return level
        seq = list(chain.from_iterable(s for s in seq if isinstance(s, Sequence)))

Та же идея, но с гораздо меньшим объемом памяти:

from collections import Sequence
from itertools import chain, count

def depth(seq):
    seq = iter(seq)
    try:
        for level in count():
            seq = chain([next(seq)], seq)
            seq = chain.from_iterable(s for s in seq if isinstance(s, Sequence))
    except StopIteration:
        return level
    
ответ дан pillmuncher 18.05.2011 в 07:23
источник
21

Вот один из способов записи функции

depth = lambda L: isinstance(L, list) and max(map(depth, L))+1

Я думаю, что вам не хватает идеи использовать max()

    
ответ дан John La Rooy 18.05.2011 в 04:10
источник
8

Давайте сначала немного перефразируем ваши требования.

  

Глубина списка - это больше, чем максимальная глубина его подписок.

Теперь это можно перевести непосредственно в код:

def depth(l):
    if isinstance(l, list):
        return 1 + max(depth(item) for item in l)
    else:
        return 0
    
ответ дан hammar 18.05.2011 в 04:12
источник
5

легко с рекурсией

def flat(l):
    depths = []
    for item in l:
        if isinstance(item, list):
            depths.append(flat(item))
    if len(depths) > 0:
        return 1 + max(depths)
    return 1
    
ответ дан Eduardo 18.05.2011 в 04:10
источник
2

Это в одной строке python:)

пользоваться

def f(g,count=0): return count if not isinstance(g,list) else max([f(x,count+1) for x in g])
    
ответ дан systemizer 18.05.2011 в 04:21
источник
1

Оскорбительный способ: Скажем, ваш список называется mylist
mybrackets = map(lambda x: 1 if x=='[' else -1, [x for x in str(mylist) if x=='[' or x==']'])
maxdepth = max([sum(mybrackets[:i+1]) for i in range(len(mybrackets))])

Это преобразует ваш список в список открывающих и закрывающих скобок, а затем находит наибольшее количество открывающих скобок, которые происходят до того, как произойдет соответствующая закрывающая скобка.

    
ответ дан sans 18.05.2011 в 04:44
источник
1

Способ, который не требует каких-либо дополнительных модулей и имеет одинаковую скорость, без какой-либо глубины:

def depth(nested):
instring = False
count = 0
depthlist = []
for char in repr(nested):
    if char == '"' or char == "'":
        instring = not instring
    elif not instring and ( char == "[" or char == ")" ):
        count += 1
    elif not instring and ( char == "]" or char == ")" ):
        count -= 1
    depthlist.append(count)
return(max(depthlist))

В основном, это означает, что это преобразование списка в строку с использованием repr() . Затем для каждого символа в этой строке, равной «(» или «[», она увеличивает переменную count . Для закрывающих скобок она уменьшает count , а затем возвращает максимум, достигший count .

    
ответ дан user3315473 07.05.2014 в 19:37
источник
0

Короткое дополнение к тому, что было сказано, поэтому оно также может обрабатывать пустые списки:

def list_depth(list_of_lists):
    if isinstance(list_of_lists, list):
        if(len(list_of_lists) == 0):
            depth = 1
        else:
            depth = 1 + max([list_depth(l) for l in list_of_lists])
    else:
        depth = 0
    return depth
    
ответ дан David 21.09.2015 в 18:31
источник
0

Я добавил ответ hammar для каждого итерабельного (по умолчанию отключены строки):

def depth(arg, exclude=None):
    if exclude is None:
        exclude = (str, )

    if isinstance(arg, tuple(exclude)):
        return 0

    try:
        if next(iter(arg)) is arg:  # avoid infinite loops
            return 1
    except TypeError:
        return 0

    try:
        depths_in = map(lambda x: depth(x, exclude), arg.values())
    except AttributeError:
        try:
            depths_in = map(lambda x: depth(x, exclude), arg)
        except TypeError:
            return 0

    try:
        depth_in = max(depths_in)
    except ValueError:
        depth_in = 0

    return 1 + depth_in
    
ответ дан Marco Sulla 29.02.2016 в 12:16
источник
0

@ Решение John превосходно, но для решения проблем с пустым списком, например [] , [[]] , вам может понадобиться сделать что-то вроде этого

depth = lambda L: isinstance(L, list) and (max(map(depth, L)) + 1) if L else 1     

ответ дан onerhao 27.09.2016 в 13:31
источник