How to find the max value from an uneven list containing ints, tuples, lists

Question

Right now I'm stuck at a problem and can't seem to figure it out. I have a list/tuple, which can in turn contain many lists/tuples/ints. I need to find the maximum value out of the object, and hence I need to look into all levels inside the object. As an example, I have the item:

(5, (1,2), [[1],[2]])

I need to write a function which returns me 5, which is the max value inside the object.

Few more examples:

([[2, 1, 5], [4, 2], 6], ([2, 1], (7, 7, 5), 6))

Function should return 7

((4,), (2,), (6, 2), (3, 6, 2))

Function should return 6

[[[[[[6]]]]]]

Function should return 6

Edit 1:

I did try this myself. This is how I thought to solve it.

def function1(x): 

global flatList    
flatList = []

for i in x:
    if type(i) is int or type(i) is float:
        flatList.append(i)
    else:
        max_val(i)

if len(flatList) != 0:
    return max(flatList)

I used Python Tutor to see what is wrong with my code, and I know that every time I recursively call my function, the flatList variable is getting assigned back to an empty list, and hence, the flatList will only contain the element from the last recursive call, if I am guessing correctly. I also cannot create the flatList variable outside the function, as it is one of the requirements of the assignment that I do not create any global variables of my own.

Answer 1

Let’s try to tackle the problem together: You probably do know how to get the maximum value of a non-nested iterable (being it a list, tuple, or whatever). You can use the built-in max() function, or alternatively write your own if you may not use a built-in function for your task.

We’ll assume for now that we have a max function (self-written or not) that accepts a non-nested iterable and returns the maximum, e.g:

>>> max([2, 1, 5])
5
>>> max((7, 7, 5))
7

So we know how to solve this for the easiest case: non-nested iterables. Now let’s go one level up: We have an iterable of iterables, for example this:

lst = [[2, 1, 5], [4, 2]]

How do we get the maximum here? We first get the maximum for each sublist and then get the maximum of all calculated maximums. Something like this:

maximums = []
for sublist in lst:
    maximums.append(max(sublist))
print(max(maximums)) # 5

So far so good. Now let’s assume that our list lst also contains single numbers, so it’s an uneven list:

lst = [[2, 1, 5], 8, [4, 2], 2]

So when we loop through the items of the list, we need to either just take the number or calculate the maximum for the sublist:

maximums = []
for item in lst:
    if isinstance(item, int):
        # item is a number itself, so it’s the maximum of itself
        maximums.append(item)
    else:
        maximums.append(max(sublist))
print(max(maximums)) # 8

So now we have the ability to max an iterable that contains mixed values. Now what we need to do is make sure that this works for any level of nestedness. For this purpose, we use recursion: We start at the outermost list and iterate through its items. When the item is a number, we can just keep the number. When its an iterable, we calculate its maximum using our solution. Afterwards we get the maximum of all collected maximums:

def nested_max(iterable):
    maximums = []
    for item in iterable:
        if isinstance(item, int):
            # still nothing to do with simple numbers
            maximums.append(item)
        else:
            # we encountered an iterable but we do not know how deep it is; so instead of
            # using the simple `max` function, we use our `nested_max` function recursively
            maximums.append(nested_max(item))

    # maximums only contains numbers, so we can use the normal `max` here
    return max(maximums)

And that’s it! Let’s give it a try:

>>> nested_max((5, (1,2), [[1],[2]]))
5
>>> nested_max(([[2, 1, 5], [4, 2], 6], ([2, 1], (7, 7, 5), 6)))
7
>>> nested_max(((4,), (2,), (6, 2), (3, 6, 2)))
6
>>> nested_max([[[[[[6]]]]]])
6

Answer 2

If you don't mind an external library you could use deepflatten from iteration_utilities (disclaimer: I'm the author) and pythons max function.

from iteration_utilities import deepflatten

a = (5, (1,2), [[1],[2]])
b = ([[2, 1, 5], [4, 2], 6], ([2, 1], (7, 7, 5), 6))
c = ((4,), (2,), (6, 2), (3, 6, 2))
d = [[[[[[6]]]]]]

>>> max(deepflatten(a))
5
>>> max(deepflatten(b))
7
>>> max(deepflatten(c))
6
>>> max(deepflatten(d))
6

A rough pure-python equivalent of deepflatten can be found in the linked documentation. It is:

def deepflatten(iterable, depth=None, types=None, ignore=None):
    if depth is None:
        depth = float('inf')
    if depth == -1:
        yield iterable
    else:
        for x in iterable:
            if ignore is not None and isinstance(x, ignore):
                yield x
            if types is None:
                try:
                    iter(x)
                except TypeError:
                    yield x
                else:
                    for item in deepflatten(x, depth - 1, types, ignore):
                        yield item
            elif not isinstance(x, types):
                yield x
            else:
                for item in deepflatten(x, depth - 1, types, ignore):
                    yield item