Find indices of elements with equal values in a matrix (Python)-CodePudding

I am trying to find the indices of all the equal elements in a matrix (n×m). For each pair of the matching cells, I will perform a specific function on them. For example:

[ [2, 1, 3], [4, 1, 5], [2, 3, 2] ]

The cell (1, 1) whose value is 2 matches with cells (3, 1) and (3, 3). I tried to do this by looping through the whole matrix twice which is far away from being efficient O(n^2 * m^2). Is there a more efficient way to do this search (at least to avoid duplicates)? Please avoid using libraries like NumPy. My code:

for i in range(n):
    for k in range(n):
        for j in range(m):
            for l in range(m):
                if matrix[i][j] == matrix[k][l]:
                    sum  = func((i   1, j   1), (k   1, l   1))
print(sum // 2)

CodePudding user response：

One approach would be to store all indices for each value like this:

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

result = {}

for i in range(len(lst)):
    for j in range(len(lst[i])):
        current = lst[i][j]
        if current in result:
            result[current].append((i   1, j   1))
        else:
            result[current] = [(i   1, j   1)]
        
result

The result is following dictionary storing the indices for all values:

{2: [(1, 1), (3, 1), (3, 3)],
 1: [(1, 2), (2, 2)],
 3: [(1, 3), (3, 2)],
 4: [(2, 1)],
 5: [(2, 3)]}

With this dictionary you can easily find values with multiple indices. One approach would be the following, where y contains all combinations of two duplicate values:

from itertools import combinations

for x in result.values():
    if (len(x) > 1):
        combis = combinations(x, 2)
        for y in combis:
            print(y)

Output:

((1, 1), (3, 1))
((1, 1), (3, 3))
((3, 1), (3, 3))
((1, 2), (2, 2))
((1, 3), (3, 2))

CodePudding user response：

Same idea as in Jano's answer,but defaultdict as it seems as a use case for it.

Build a dict in which the 'keys' are lst elements and 'values' are a list of locations.

from collections import defaultdict

result = defaultdict(list)
for i, sublst in enumerate(lst):
    for j, value in enumerate(sublst):
        result[value].append((i,j))

Then you can use result for whatever you want

>>> print('\n'.join(', '.join(str(location) for location in locations)
               for locations in result.values() if len(locations) > 1))
(0, 0), (2, 0), (2, 2)
(0, 1), (1, 1)
(0, 2), (2, 1)

Note: Indexes are 0-based as per Python common usage.

CodePudding user response：

Here's an alternate solution (note that it gives the actual indices of your items, since Python is zero-indexed):

m = [[2, 1, 3], [4, 1, 5], [2, 3, 2]]
flat_m = [item for inner in m for item in inner]
unique_m = set(flat_m)

out = {}
for item in unique_m:
    out[item] = [divmod(idx, len(m)) for idx, val in enumerate(flat_m) if val == item]

Output:

{1: [(0, 1), (1, 1)],
 2: [(0, 0), (2, 0), (2, 2)],
 3: [(0, 2), (2, 1)],
 4: [(1, 0)],
 5: [(1, 2)]}

CodePudding user response：

You can use itertools.combinations. Creating list with row and column indexes, then apply combinations and check for the sum output will be like

(row_idx_1st_ele, col_idx_1st_ele, row_idx_2nd_ele, col_idx_2nd_ele)

If you don't want to match with in the same row update if confition like this if x[0] != y[0] and x[-1] == y[-1]

Code:

from itertools import combinations

lst = [ [2, 1, 3], [4, 1, 5], [2, 3, 2] ]
index_lst = [(ridx, cidx, col) for ridx, row in enumerate(lst) for cidx, col in enumerate(row)]

res = [(*x[:-1], *y[:-1]) for x, y in combinations(index_lst, 2) if x[-1] == y[-1]]
print(res)

Output:

[(0, 0, 2, 0), (0, 0, 2, 2), (0, 1, 1, 1), (0, 2, 2, 1), (2, 0, 2, 2)]