CODEWITHSUNDEEP
pythonalgorithm
MohannedUsama
MohannedUsama

Reputation: 21

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

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)

Upvotes: 0

Views: 394

Answers (2)

hpchavaz
hpchavaz

Reputation: 1388

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.

Upvotes: 1

JANO
JANO

Reputation: 3066

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))

Upvotes: 1

Related Questions