CODEWITHSUNDEEP
pythonlist
a2warik
a2warik

Reputation: 143

Need to find a maximum in a list of lists

I found this question in 'How to Think like a computer scientist: Learning with Python 3, 3rd edition' by Peter Wentworth. I have added their solution below as well.

My simple recursive function produces wrong output

def maximum_in_list(L):
    '''Finds the maximum value from L which is a List_of_List'''
    item=0
    for i in L:
        if type(i)==list:
            item=maximum_in_list(i)
        elif i>item:
            item=i
    return item

print(maximum_in_list([9,18,99,7,4,21,[3,5,[27,57,92],7,76],32,4]))
print(maximum_in_list([2, 9, [1, 13], 8, 6]))
print(maximum_in_list([2, [[100, 7], 90], [1, 13], 8, 6])) #Here the problem occurs
print(maximum_in_list([[[13, 7], 90], 2, [1, 100], 8, 6]))

The Books Code produces the correct one, but why the need of a flag?

def r_max(nxs):
   largest=None
   first_time=True
   for e in nxs:
       if type(e)=type([]):
           val=r_max(e)
       else:
           val=e
       if first_time or val>largest:
           largest=val
           first_time=False
   return largest

I am unable to understand the requirement of a flag here, though it produces the correct result.

Upvotes: 2

Views: 151

Answers (4)

Ma0
Ma0

Reputation: 15204

Here is a neat fix of your function:

def maximum_in_list(L):
    '''Finds the maximum value from L which is a List_of_List'''
    item = -float('inf')
    for i in L:
        if isinstance(i, list):
            i = maximum_in_list(i)  # see remark
        item = max(item, i)
    return item

Remark:

when i is a list you can re-assign it to the max of that list (recursively) so that you do not have to use too many if statements further down.

print(maximum_in_list([9,18,99,7,4,21,[3,5,[27,57,92],7,76],32,4]))  # ->  99
print(maximum_in_list([2, 9, [1, 13], 8, 6]))                        # ->  13
print(maximum_in_list([2, [[100, 7], 90], [1, 13], 8, 6]))           # -> 100
print(maximum_in_list([[[13, 7], 90], 2, [1, 100], 8, 6]))           # -> 100

Upvotes: 1

PM 2Ring
PM 2Ring

Reputation: 55469

Here's a more compact recursive solution which uses a generator expression and the built-in max function. It handles negative values correctly, and it will also work with non-numeric data. However, it will raise TypeError if you pass it a list containing items that can't be compared, eg numbers and strings.

def r_max(lst):
    return max(r_max(u) if isinstance(u, list) else u for u in lst)

# test

data = (
    [9,18,99,7,4,21,[3,5,[27,57,92],7,76],32,4],
    [2, 9, [1, 13], 8, 6],
    [2, [[100, 7], 90], [1, 13], 8, 6],
    [[[13, 7], 90], 2, [1, 100], 8, 6],
    [[[-13, -7], -90], -2, [-1, -100], -8, -6],
    ['abc', 'd', ['ef', 'ghi', ['jkl', 'zzz'], 'xy', 'z']],
)

for lst in data:
    print(lst)
    print(r_max(lst))

output

[9, 18, 99, 7, 4, 21, [3, 5, [27, 57, 92], 7, 76], 32, 4]
99
[2, 9, [1, 13], 8, 6]
13
[2, [[100, 7], 90], [1, 13], 8, 6]
100
[[[13, 7], 90], 2, [1, 100], 8, 6]
100
[[[-13, -7], -90], -2, [-1, -100], -8, -6]
-1
['abc', 'd', ['ef', 'ghi', ['jkl', 'zzz'], 'xy', 'z']]
zzz

Upvotes: 2

Venkata Gogu
Venkata Gogu

Reputation: 1051

There is a problem with your recursive approach. Simple fix would be:

item = max(item, maximum_in_list(i))

Updated code would look like this:

def maximum_in_list(L):
    '''Finds the maximum value from L which is a List_of_List'''
    item=0
    for i in L:
        if type(i)==list:
            item=max(item, maximum_in_list(i))
        elif i>item:
            item=i
    return item

print(maximum_in_list([9,18,99,7,4,21,[3,5,[27,57,92],7,76],32,4]))
print(maximum_in_list([2, 9, [1, 13], 8, 6]))
print(maximum_in_list([2, [[100, 7], 90], [1, 13], 8, 6])) #Here the problem occurs
print(maximum_in_list([[[13, 7], 90], 2, [1, 100], 8, 6]))

The first time flag is used to prevent comparing a None value to an integer. If you do a comparison without first_time check then it results Type Error.

Upvotes: 3

Gaurav Goswami
Gaurav Goswami

Reputation: 32

The flag makes sure that the item variable is not reset to 0 every time, thereby producing problematic output. Your code suffers from the problem that whenever the function is called for a sub-list it resets the item variable and then compares for the maximum with 0 instead of the old maximum.

In your problematic input, if you change the position of 6 and 100 you will get the correct output because the last sub-list has been dealt with by then. If you add another sub-list after the now changed 100 (in the position of 6), then you'll again get the problem to occur.

Upvotes: -1

Related Questions