Finding coordinates of maximum value in a grid

user_9859930 0
Viewed 3368

Given a grid of numbers like

g=[[2, 2, 2, 3, 2],
   [2, -1, -1, 3, 3],
   [3, 2, -1, 3, 3],
   [2, 4, 3, 3, 3],
   [-1, 2, 2, -1, 1]]

i am searching for the maximum value in that 2d list, which, in this example, is obivously 4. To find that, max(max(graph,key=max)) does the job (even though i know it calls max for the line with the maximum value twice, so it is not perfectly efficient)

But that is only half what i am looking for. I need the coordinates of this 4. I would like to have a short, efficient and pythonic piece of code like x, y = find_2d_max_index(g) that gives me the position of the max number, without doing the triple max thing before. I want to avoid to use the index() method after finding the max as that would be very inefficient.

I looked into numpy argmax, but could not get it to work in this application with a 2d list.

Any help is appreciated.

python-3.x list
4 Answers

You can use numpy for this and the documentation illustrates how.

import numpy as np

a = np.array([[2, 2, 2, 3, 2],
   [2, -1, -1, 3, 3],
   [3, 2, -1, 3, 3],
   [2, 4, 3, 3, 3],
   [-1, 2, 2, -1, 1]])

idx = np.unravel_index(np.argmax(a), a.shape)

a[idx]
>> 4

Explanation: We use argmax with no axis defined to get the index of the maximum item if the array were one flat array, in this case it would be 16 as the number 4 would be the 16th element of this long array. Then we provide the shape of our actual array to np.unravel_index and the index of the max item, in this case 16 and it determines based on the shape of the array, the coordinates of this number.

user_68178350

If all "rows" in graph have the same length (making graph equivalent to a 2D numpy array), then you can simply find the position of the largest value in a linear expansion and infer the coordinates from the position and the number of "columns" in graph (this is how numpy works under the hood).

import operator as op
from itertools import chain

ncol = len(graph[0])
flattened = chain.from_iterable(graph)
max_idx, max_val = max(enumerate(flattened), key=op.itemgetter(1))
row = max_idx // ncol
col = max_idx % ncol

# a simple sanity check
assert graph[row][col] == max_val
user_38462130

you could use max and enumerate built-in fucntions:

(col, val), row = max(map(lambda x: (max(enumerate(x[1]), key= lambda x: x[1]), x[0]), enumerate(g)), key=lambda x: x[0][1])
print(col, row)

output:

1 3

to break this apart you could use:

from typing import List, Tuple

# didn't get the inner functions out to be easy to read/understand
def max_row_with_column_and_row_coordinates(row_list: tuple):
        """Given row number and the value return the max on each row

        with the row number and column number
        """

        def get_max_row(row_list: Tuple[int, List]) -> Tuple[Tuple[int, int], int]:
            row_number, inner_list = row_list
            # will give you the col number and the actual number/value
            col_value = enumerate(inner_list)  # (col_number, number)

            def get_value(col_value: Tuple[int, int]) -> int:
                col_number, value = col_value
                return value

            col_max_row = max(col_value, key=get_value)

            return col_max_row, row_number # ((col_number, value), row_number)

        def get_the_value(col_value_row: Tuple[Tuple[int, int], int]) -> int:
            (col_number, value), row_numebr = col_value_row # unpack
            return value

        max_row_with_coordinates = map(get_max_row, row_list)

        return max(max_row_with_coordinates, key=get_the_value)  # ((col_number, value), row_numebr) 


def max_value_with_coordinates(g: List[List]) -> Tuple[Tuple[int, int], int]:
    """Return the max on each row keeping the coordinates of each value.

    The coordinates are given by the enumerate built-in function.
    """

    row_list = enumerate(g) # will give you the row number: (row_numebr, inner_list)
    return max_row_with_column_and_row_coordinates(row_list) # ((col_number, value), row_numebr) 

(col, val), row = max_value_with_coordinates(g)

print(col, row)

output:

1 3
user_31615750

Just do the following:

max(map(max, graph))

This will call max only once for each row and then take the max from the results.

user_23901820
Related