关于寻找任意嵌套列表的最大深度 [英] On Finding the Maximum Depth of an Arbitrarily Nested List

问题描述

我目前正在 Python 中使用递归函数，但遇到了障碍.如题，问题是返回任意嵌套列表的最大深度.

I'm currently working with a recursive function in Python, and I've run into a wall. As titled, the problem is to return the maximum depth of an arbitrarily nested list.

这是我目前所拥有的:

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

我觉得问题出在我的递归调用上(这可能很明显).当列表到达末尾时它确实会返回 var，但是当我有一个非空列表时，事情就会出错.根本没有返回任何东西.

I feel that the problem is with my recursive calls (this may be obvious). 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.

我切片错了吗?我应该在递归调用的切片之前做些什么吗?

Am I slicing wrong? Should I be doing something before the slice in the recursive call?

问题也可能出在我的基本案例上.

The problem may also be with my base case.

推荐答案

如果它们只是嵌套列表，例如 [[[], []], [], [[]]]，这是一个很好的解决方案:

If they are just nested lists, e.g., [[[], []], [], [[]]], here's a nice solution:

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

如果您不使用 Python 3.4，您可以使用这里的一个小变化，其中引入了 default 参数:

Here's a slight variation you could use if you don't use Python 3.4, where the default argument was introduced:

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

它们的计数方式也有所不同.第一个认为空列表的深度为 1，第二个认为深度为 0.第一个很容易适应，不过，只需将默认值设为 -1.

They also differ by how they count. The first considers the empty list to be depth 1, the second to be depth 0. The first one is easy to adapt, though, just make the default -1.

如果它们不仅仅是嵌套列表，例如 [[[1], 'a', [-5.5]], [(6,3)], [['hi']]]) ，以下是对此的改编:

If they're not just nested lists, e.g., [[[1], 'a', [-5.5]], [(6,3)], [['hi']]]), here are adaptions to that:

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

确保您了解后者的工作原理.如果你还不知道，它会教你 和 在 Python 中是如何工作的 :-)

Make sure you understand how the latter one works. If you don't know it yet, it'll teach you how and works in Python :-)

接受纯粹递归"的挑战:

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

当然，额外的参数有点难看，但我认为还可以.

Granted, the extra argument is slightly ugly, but I think it's ok.

这篇关于关于寻找任意嵌套列表的最大深度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！