(python) Найти наибольшую группу соприкасающихся друг с другом элементов двумерного массива
У меня имеется код, вычисляющий наибольшее количество соприкасающихся одинаковых элементов двумерного массива (Но только, если задать этот элемент внутри функции (у меня это (def count_region_cells(matrix, row, col))
Это весь код:
def checkio(matrix):
def maxRegion(matrix):
max_cell_counter = 0
for row in range(len(matrix)):
for col in range(len(matrix[0])):
region_cell_count = count_region_cells(matrix, row, col)
max_cell_counter = max(max_cell_counter, region_cell_count)
return max_cell_counter
def count_region_cells(matrix, row, col):
if any([row<0, col<0, row >= len(matrix), col >= len(matrix[0])]):
return 0
if matrix[row][col] != 1:
return 0
cell_count = 1
matrix[row][col] = 0
for r in range(row - 1, row + 2):
for c in range(col - 1, col + 2):
if any([r == row, c == col]):
cell_count += count_region_cells(matrix, r, c)
return cell_count
return maxRegion(matrix)
Внутри этой функции есть строчка, обозначающая, какой элемент мне нужно рассматривать (в моём случае это 1 (т.е. если в ближайших клетках по вертикали и горизонтали больше нету единичек, то функция завершает свою работу)) (ДИАГОНАЛИ НЕ УЧИТЫВАЕМ):
Отрывок функции, которая ищет соседей (но только соседей единички):
def count_region_cells(matrix, row, col):
if any([row<0, col<0, row >= len(matrix), col >= len(matrix[0])]):
return 0
if matrix[row][col] != 1:
return 0
У меня то ли мозг перегрелся, то ли что, но я никак не могу сделать так, чтобы функция учитывала ВСЕ элементы массива, а не только заданный внутри функции и возвращала максимальное количество соприкасающихся одинаковых элементов. Как подобное можно провернуть?
Пример матрицы:
[[1,1,5,1,1,4,2],
[2,4,3,2,3,4,5],
[1,5,4,4,4,1,1],
[1,4,4,2,5,1,3],
[4,4,1,1,1,5,3],
[4,2,1,3,5,3,3],
[4,5,2,1,4,5,5]]
Правильным ответом для неё является [4, 9] (четвёрка соседствует с другими четвёрками 9 раз; остальные элементы соседствуют меньше 9 раз)
Воть так воть (заменил остальные элементы на нолик для наглядности):
[[0,0,0,0,0,0,0],
[0,0,0,0,0,0,0],
[0,0,4,4,4,0,0],
[0,4,4,0,0,0,0],
[4,4,0,0,0,0,0],
[4,0,0,0,0,0,0],
[4,0,0,0,0,0,0]]
Ответы (1 шт):
Если не использовать высокоуровневые библиотеки типа scipy (scipy.ndimage.label решает эту задачу в одну строку), а попробовать сделать "руками", на ум приходит несколько способов: например, получать координаты значений и вложенными циклами искать пересечения и смежные (долго). Либо, с помощью библиотек верхнего уровня (matplotlib - contour) построить отдельные контуры смежных значений и искать пересечения контуров со значениями в исходной матрице (не точно). Но вот я бы сделал с помощью свертывания по евклидовым расстояниям:
import numpy as np
matrix = np.array([
[1, 1, 5, 1, 1, 4, 2],
[2, 4, 3, 2, 3, 4, 5],
[1, 5, 4, 4, 4, 1, 1],
[1, 4, 4, 2, 5, 1, 3],
[4, 4, 1, 1, 1, 5, 3],
[4, 2, 1, 3, 5, 3, 3],
[4, 5, 4, 1, 4, 5, 5]
])
# получаем евклидовы расстояния между элементами матрицы с заданным значением
# оставляем только раыные единице (смежные точки)
# 0 (расстояние до самой себя) заменяем на единицу для того, чтобы сработала конволюция
def euc_dist(matrix):
res = [np.sqrt(np.sum(np.square(elem-matrix), axis=1)) for elem in matrix]
res = np.where(np.isin(np.array(res), (0, 1)), 1, 0)
return res
# что-то вроде конволюции - складываем каждую строку матрицы расстояний
# с оставшимися строками, если у них есть общий элемент
# если общих нет - заноим индекс строки в список, затем сокращаем матрицу до
# этого списка для итераций по другим значениям
def conv_custom(matrix):
indices = []
idx = 0
sample = matrix[0]
for elem in matrix[1:]:
idx+=1
if sum(sample & elem):
sample= sample | elem
else:
indices.append(idx)
matrix=matrix[indices]
return sample, matrix
# нормальзиция матрицы по искомому элементу, получение координат искомого значения
# поиск цепочек
def find_chains(matrix, search_value):
_matrix = matrix.copy()
_matrix = np.where(_matrix==search_value, 1, 0)
coords = np.argwhere(_matrix==1)
euclidean = euc_dist(coords)
chains = []
while len(euclidean):
sample, euclidean = conv_custom(euclidean)
chains.append(sample)
return np.array(chains)
def main():
vals = np.unique(matrix) # все уникальные значения матрицы
all_chains={}
# поиск цепочек, заполнение словаря
for val in vals:
search_value = val
all_chains[search_value] = find_chains(matrix, search_value)
longest_chains={}
# получение длиннейших цепочек для каждого значения
for key in all_chains.keys():
res = sorted(all_chains[key], key=sum)[-1]
longest_chains[key]=sum(res)
# полуяение длиннейшей цепочки из всех значений
longest = max(longest_chains, key=longest_chains.get)
final = f"value {longest} has the longest contiguous chain of {longest_chains[longest]} elements."
print(final)
# make_graph(all_chains, longest, final) - визуализация
if __name__ =="__main__":
main()
value 4 has the longest contiguous chain of 9 elements.
при желании можно сделать визуализацию:
def make_graph(all_chains, longest, final):
import matplotlib.pyplot as plt
import seaborn as sns
fig, axs = plt.subplots(1,2, figsize=(12,6))
sns.heatmap(matrix, annot=True, ax=axs[0], cbar=False, xticklabels=False, yticklabels=False, cmap="PuBu")
_chain = sorted(all_chains[longest], key=sum)[-1]
_coords = coords[np.where(_chain==1)]
_matrix = np.zeros(matrix.shape, dtype=int)
_matrix[_coords[:,0], _coords[:,1]] = np.ones(len(_coords), dtype=int)
sns.heatmap(_matrix, annot=matrix, ax=axs[1], cbar=False, xticklabels=False, yticklabels=False ,cmap="PuBu")
fig.suptitle(final, fontsize=16)
plt.show()
