Глубина подсчета или самый глубокий уровень вложенного списка
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...
Любые идеи или помощь будут очень благодарны ^^ спасибо много! Я боролся с этим уже несколько недель...
Ответы
Ответ 1
Ширина - сначала без рекурсии, а также работает с другими типами последовательностей:
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
Ответ 2
Вот один из способов записи функции
depth = lambda L: isinstance(L, list) and max(map(depth, L))+1
Я думаю, что вам не хватает идеи использовать max()
Ответ 3
Давайте сначала немного перефразируем ваши требования.
Глубина списка - это больше, чем максимальная глубина его подписок.
Теперь это можно перевести непосредственно в код:
def depth(l):
if isinstance(l, list):
return 1 + max(depth(item) for item in l)
else:
return 0
Ответ 4
легко с рекурсией
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
Ответ 5
Это в одной строке python:)
пользоваться
def f(g,count=0): return count if not isinstance(g,list) else max([f(x,count+1) for x in g])
Ответ 6
Оскорбительный способ:
Скажем, ваш список называется 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))])
Это преобразует ваш список в список открывающих и закрывающих скобок, а затем находит наибольшее количество открывающих скобок, которые происходят до того, как произойдет соответствующая закрывающая скобка.
Ответ 7
Способ, который не требует никаких дополнительных модулей и имеет одинаковую скорость, независимо от глубины:
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
достиг.
Ответ 8
Я добавил hammar answer для каждого итерабельного (по умолчанию отключены строки):
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
Ответ 9
Короткое дополнение к тому, что было сказано, поэтому оно также может обрабатывать пустые списки:
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
Ответ 10
Решение @John отлично, но для решения проблем с пустым списком, например []
, [[]]
, вам может понадобиться сделать что-то вроде этого
depth = lambda L: isinstance(L, list) and (max(map(depth, L)) + 1) if L else 1
Ответ 11
В Numpy вы можете преобразовать структуру данных в numpy array
и использовать его библиотечные функции. arr.shape
дает длину на слой, поэтому мы можем len()
форму и получить глубину структуры:
import numpy as np
def f( lists )
arr = np.array( lists )
return len(arr.shape)
f( [[[1,2],[3,4]],[[3,4],[5,6]]] ) # results in 3
f( [[1,2],[3,4]] ) # results in 2
f( [1,2] ) # results in 1
f( [] ) # results in 1
Numpy документы для формы: https://docs.scipy.org/doc/numpy/reference/generated/numpy.ndarray.shape.html