CODEWITHSUNDEEP
pythonrecursion
Faisal
Faisal

Reputation: 11

I am trying to make a function which return max from nested list?

I wrote this and its working fine with everything but when I have an empty list in a given list(given_list=[[],1,2,3]) it saying index is out of range. Any help?

def r_max (given_list):
    largest = given_list[0]
    while type(largest) == type([]):
        largest = largest[0]

    for element in given_list:
        if type(element) == type([]):
            max_of_elem = r_max(element)
            if largest < max_of_elem:
                largest = max_of_elem
        else:                           # element is not a list
            if largest < element:
                largest = element

    return largest

Upvotes: 1

Views: 1223

Answers (6)

Zelin
Zelin

Reputation: 1

I assume that the max element of an empty list is negative infinity.

This assumption will deal with the cases like [], [1,2,[],5,4,[]]

def find_max(L):

    if len(L) == 0:
        return float("-inf")
    elif len(L) == 1:
        if isinstance(L[0], list):
            return find_max(L[0])
        else:
            return L[0]
    elif len(L) == 2:
        if isinstance(L[0], list):
            firstMax = find_max(L[0])
        else:
            firstMax = L[0]
        if isinstance(L[1], list):
            lastMax = find_max(L[1])
        else:
            lastMax = L[1]
        if firstMax > lastMax:
            return firstMax
        else:
            return lastMax
    else:
        if isinstance(L[0], list):
            firstMax = find_max(L[0])
            lastMax = find_max(L[1:])
            if firstMax > lastMax:
                return firstMax
            else:
                return lastMax
        else:
            lastMax = find_max(L[1:])
            if L[0] > lastMax:
                return L[0]
            else:
                return lastMax

Upvotes: 0

Padmal
Padmal

Reputation: 478

This will find the maximum in a list which contains nested lists and ignore string instances.

A = [2, 4, 6, 8, [[11, 585, "tu"], 100, [9, 7]], 5, 3, "ccc", 1]

def M(L):

    # If list is empty, return nothing
    if len(L) == 0:
        return

    # If the list size is one, it could be one element or a list
    if len(L) == 1:

        # If it's a list, get the maximum out of it
        if isinstance(L[0], list):
            return M(L[0])
        # If it's a string, ignore it
        if isinstance(L[0], str):
            return
        # Else return the value
        else:
            return L[0]

    # If the list has more elements, find the maximum
    else:
        return max(M(L[:1]), M(L[1:]))


print A
print M(A)

Padmal's BLOG

Upvotes: 0

Dan
Dan

Reputation: 1362

If you're confident that there will only be one level of nesting in there, you could do something like 

def r_max(lst):
    new_lst = []
    for i in lst:
        try:
            new_lst.extend(i)
        except TypeError:
            new_lst + [i]
    return max(new_lst)

But I'm not in love with that solution - but it might inspire you to come up with something nicer.

Two things I'd like to highlight about this solution, in contrast to yours:

  1. All the type-checking you're doing (type(largest) == type([]), etc.) isn't considered idiomatic Python. It works, but one of the key points of Python is that it promotes duck typing/EAFP, which means that you should be more concerned with what an object can do (as opposed to what type it is), and that you should just try stuff and recover as opposed to figuring out if you can do it.
  2. Python has a perfectly good "find the largest number in a list" function - max. If you can make your input a non-nested list, then max does the rest for you.

Upvotes: 0

Alex Martelli
Alex Martelli

Reputation: 882171

If the nesting is arbitrarily deep, you first need recursion to untangle it:

def items(x):
    if isinstance(x, list):
        for it in x:
            for y in items(it): yield y
    else: yield x

Now, max(items(whatever)) will work fine.

In recent releases of Python 3 you can make this more elegant by changing

        for it in x:
            for y in items(x): yield y

into:

        for it in x: yield from it

Upvotes: 0

Jthorpe
Jthorpe

Reputation: 10194

that error indicates your index is out of range, which is the case with the first element of your example. The solution is not to iterate over lists of length zero:

def r_max (given_list):
    largest = given_list[0]
    while type(largest) == type([]):
        largest = largest[0]

    for element in given_list:
        if type(element) == type([]):
            # If the list is empty, skip
            if(len(elemnt) == 0)
                next
            max_of_elem = r_max(element)
            if largest < max_of_elem:
                largest = max_of_elem
        else:                           # element is not a list
            if largest < element:
                largest = element

    return larges

while your at it, you might want to assert len(given_list)>0 or something equivalent.

Upvotes: 1

Benson Zhang
Benson Zhang

Reputation: 135

You are assuming given_list has at least 1 element which is incorrect. To avoid index out of range, you may add

if (len(given_list) == 0)
  return None

to the beginning of your function.

Upvotes: 1

Related Questions