Python - 使用递归在嵌套列表中查找最大值和最小值的和

Question

这是我目前了解到的一切... 我无法弄清楚我做错了什么。

首先是我的辅助函数。

def max_min(l):

    if isinstance (l[0], list):
        result = max_min(l[0])

    elif len(l) == 2:
        if l[0] < l[1]:
            result = l[0], l[1]
        else:
            result = l[1], l[0]

    else:
        Min, Max = max_min(l[1:])
        if l[0] <= Min:
            result = l[0], Max
        elif l[0] >= Max:
            result = Min, l[0]
        else:
            result = Min, Max

    return result

尝试进行此操作时：

l = [6, 3, 7, 5, 5, 2, [3, 2], 1]
print max_min(l)

它给我(2, 7)，但我预期的是(1, 7)

我已经没有更多的想法了...有人可以指出方向吗？

- user984343

---

使用递归对应用程序是否至关重要？将其转换为一个列表，然后排序并取第一个和最后一个元素会更简单。 - Tom

运行您的代码通过调试器，看看它在哪里表现不像您所期望的那样。 - Vincent Savard

这是作业吗？在真正的代码中没有理由这样做。 - Daenyth

是的，这是一道作业题...好吧，练习题~ 我们不允许多次遍历列表。 - user984343

@user984343。在这种情况下，这是XY问题。递归并不是最好的选择。不过，你尝试了并且差点自己解决了问题，这点值得肯定。 - Mad Physicist

Answer 1

当程序遇到嵌套列表时，它会停止评估其他元素。块if isinstance(l[0], list)确保如果有嵌套列表，则不会评估剩余的元素，因为Min, Max = max_min(l[1:])永远不会被调用。

您可以使用以下内容修复if块：

if isinstance (l[0], list):
    Nested_Min, Nested_Max = max_min(l[0])
    Remainder_Min, Remainder_Max = max_min(l[1:])
    Min = Nested_Min if Nested_Min < Remainder_Min else Remainder_Min
    Max = Nested_Max if Nested_Max > Remainder_Max else Remainder_Max
    result = Min, Max

您还应该将检查 if len(l) == 2 替换为：

if len(l) == 1:
    result = l[0], l[0]

这样你的函数将不会因为单元素列表而失败。最后，在开头添加类似以下内容：

if not l:
    return ()

- Mad Physicist

---

@user984343。在这种情况下，也许选择这个答案是适当的。 - Mad Physicist

Answer 2

可以试试这个：

def min_max(l):
    if isinstance(l, list):
        t = [min_max(v) for v in l]
        return min([m[0] for m in t]), max([m[1] for m in t])
    else:
        return l, l

示例输出：

>>> l = [6, 3, 7, 5, 5, 2, [3, 2], 1]
>>> min_max(l)
(1, 7)
>>>

请注意，空列表或子列表会导致错误，因此如果您关心这一点，您可能需要添加一个检查。

- Tom Karzes

---

@sedavidw。那绝对不是真的。这些函数会在嵌套列表上出错。 - Mad Physicist

我撤回之前的评论，它们事实上是不正确的。 - sedavidw

@sedavidw 你错了。试试这个：min([2, [1, 3]])。它会返回 2 而不是 1。 - Tom Karzes

OK。在Py2中工作，但答案不正确。甚至不确定它如何将列表与整数进行比较。 - Mad Physicist

@TomKarzes。你是绝对正确的。原因很混乱，是因为按字典顺序，“int” < “list”。不开玩笑：https://dev59.com/wXA75IYBdhLWcg3weZDu#3270689 - Mad Physicist

Answer 3

进一步解释我的评论，由于您的列表中混合了整数和列表，因此仍需要使用递归来展平列表，代码如下所示：

def flatten(l):
    tmp = []
    for i in l:
        if isinstance(i, int):
            tmp.append(i)
        elif isinstance(i, list):
            tmp += flatten(i)
        else:
            raise AttributeError("found unexpected type {t}".format(t=type(i)))
    return tmp

- Tom

Answer 4

你的递归函数可以同时简化和改进。请参考以下内容：

#! /usr/bin/env python3


def main():
    array = [6, 3, 7, 5, 5, 2, [3, 2], 1]
    print(sum_min_max(array))


def sum_min_max(array):
    return (lambda a, b: a + b)(*get_min_max(array))


def get_min_max(array, minimum=+float('inf'), maximum=-float('inf')):
    if array:
        head, *tail = array
        if isinstance(head, (list, tuple)):
            minimum, maximum = get_min_max(head, minimum, maximum)
        else:
            if head < minimum:
                minimum = head
            if head > maximum:
                maximum = head
        minimum, maximum = get_min_max(tail, minimum, maximum)
    return minimum, maximum


if __name__ == '__main__':
    main()

- Noctis Skytower