35

A have a real problem (and a headache) with an assignment...

I'm in an introductory programming class, and I have to write a function that, given a list, will return the "maximum" depth it goes to... For example: [1,2,3] will return 1, [1,[2,3]] will return 2...

I've written this piece of code (it's the best I could get T_T)

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

However, It obviously doens't work like it should, because if there are lists that do not count for the maximum deepness, it still raises the counter...

For example: when I use the function with [1,2,[3,4],5,[6],7] it should return 2, but it returns 3...

Any ideas or help would be greatly appreciated ^^ thanks a lot!! I've been strugling with this for weeks now...

5
  • 4
    I think the word you want is "depth", not "deepness".
    – duffymo
    May 18, 2011 at 2:05
  • 3
    As a side note: check out PEP-8. It'll be good to form style habits right away. For starters, use L for a list, not l (which looks like 1).
    – orokusaki
    May 18, 2011 at 2:29
  • 2
    @duffymo Thanks ^^ my bad, I guess it's pretty clear that English is not my first language :-)
    – dhcarmona
    May 18, 2011 at 2:49
  • 3
    @orokusaki That's really interesting ^^ thanks! I didn't know that even existed...
    – dhcarmona
    May 18, 2011 at 2:50
  • 5
    +1 for making clear that this is homework and then asking the question appropriately. The question is both interesting, and shows what's been tried so far.
    – Wilduck
    May 18, 2011 at 6:27

14 Answers 14

39

Here is one way to write the function

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

I think the idea you are missing is to use max()

4
  • Thanks ^^ I love the way you guys are able to simplify every function using lambda ^^ I hope to be able to do that someday.
    – dhcarmona
    May 18, 2011 at 2:28
  • 6
    This breaks on empty lists, just fyi Jan 11, 2017 at 0:13
  • 1
    Named lambdas are bad practice. Use a def instead: def depth(L): return isinstance(L, list) and max(map(depth, L))+1
    – wjandrea
    May 14, 2021 at 15:58
  • def depth(l): return isinstance(l, list) and max(map(depth, l)) + 1 if l else 1
    – Emil
    May 24, 2022 at 5:42
17

Let's first rephrase your requirements slightly.

The depth of a list is one more than the maximum depth of its sub-lists.

Now, this can be translated directly to code:

def depth(l):
    if isinstance(l, list):
        return 1 + max(depth(item) for item in l)
    else:
        return 0
3
  • 6
    The code needs to be corrected for empty list elements which cause the generator to create an empty sequence for max arg resulting in error. Mar 3, 2015 at 21:23
  • @Basel It looks like a minimal fix is adding if l else 1 after the max() call.
    – wjandrea
    May 14, 2021 at 16:04
  • def depth(l): return isinstance(l, list) and max(map(depth, l)) + 1 if l else 1
    – Emil
    May 24, 2022 at 5:41
9

easy with recursion

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
0
6

Breadth-first, without recursion, and it also works with other sequence types:

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

The same idea, but with much less memory consumption:

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
  • 1
    this will break on a sequence with strings. for example, depth(["a"]) will break
    – asdf
    Jul 21, 2016 at 17:30
  • simply extend the third last line like so seq = chain.from_iterable(s for s in seq if isinstance(s, Sequence) and not isinstance(s, str)) and it will also work with string elements
    – Max F.
    Jun 4, 2018 at 9:27
2

Did it in one line of python :)

enjoy

def f(g,count=0): return count if not isinstance(g,list) else max([f(x,count+1) for x in g])
2

A way that does not need any additional modules and has the same speed, no matter what depth:

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

Basically, what this does is convert the list to a string using repr(). Then for every character in this string equal to "(" or "[" it increases the variable count. for the closing brackets it decreases count. It then returns the maximum that count has reached.

2

In Numpy, you can convert the data structure to a numpy array and use its library functions. arr.shape gives length per layer, so we can len() the shape and get the depth of the structure:

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 docs for shape: https://docs.scipy.org/doc/numpy/reference/generated/numpy.ndarray.shape.html

2

Abusive way: Say your list is called 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))])

This converts your list to a list of opening and closing brackets, then finds the largest number of opening brackets that occur before the corresponding closing bracket occurs.

1

I extended the hammar's answer for every iterable (strings disabled by default):

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
0
1

If you're looking for a quick fix

def getDepth(matrix):
    try:
        len(matrix)
        return getDepth(matrix[0]) + 1
    except:
        return 0
1
  • 1
    Try putting getDepth(["222"]) into your interpreter, then....
    – Ulf Aslak
    May 17, 2021 at 13:05
1

Let's stick with the original, fairly elegant solution and get it working using max. So many of the other solutions use lambda expressions or require external libraries. This one uses 'pure' python and keeps it simple.

def depth(lst):
    d = 0
    for item in lst:
        if isinstance(item, list):
            d = max(depth(item), d)
    return d + 1

Bonus: this solution counts empty lists and avoids the trap of traversing a string (provided you want to count empty lists).

0

A short addition to what has been said so it can handle empty lists too:

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
0

you can also do it recursively using only python :

def depth(L,d):
    max = d
    for i in range(len(L)):
        if type(L[i])==list :
            a = depth(L[i],d+1)
            if a>max :
                 max = a
    return(max)

this function is recursive and what it does is that it just goes to the maximum depth of your list counting how deep the list is, and when it climbs back up, it keeps only the biggest deepness registered among all nested lists.

1
  • Two simplifications: first use the function max and lose the variables a and max; second, use a foreach loop: def depth(L, d): for itm in L: if type(itm) == list: d = max(depth(itm, d + 1), d) return d
    – Eric D
    Jan 2, 2022 at 13:41
0

@John's solution is excellent, but to address the empty list cases, like [], [[]], or further nested lists, you may need to do something like this

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.