+- Python Forum (https://python-forum.io)
+-- Forum: Python Coding (https://python-forum.io/forum-7.html)
+--- Forum: General Coding Help (https://python-forum.io/forum-8.html)
+--- Thread: Grouping algorithm (/thread-26932.html)
Grouping algorithm - riccardoob - May-19-2020
As the title says I'm trying to write a grouping algorithm, although I'm not sure if that is the right term to describe what I need. Here a better explanation: I have a matrix m rows by n columns, each cell contains a value that is either 0 or 1; I need an algorithm that, given a coordinate to a cell of the matrix, if that cell contains a '1' returns a list of the "group" of all the adjacent cells that contains '1' values plus all the adjacent cells to the cells adjacent to the first one and so on (a adjacent cell to another is a cell that i vertically, horizontally or diagonally adjacent).
Example:
matrix = [ [0, 0, 0, 0, 1], [0, 0, 0, 1, 1], [0, 0, 1, 0, 1], [0, 0, 0, 0, 0], ]In this case, given the cell
coord = (0, 4)returns this list:
group = [(0, 4), (1, 3), (1, 4), (2, 2), (2, 4)]This is the problem, I don't necessarily need an algorithm, a guidance to research about this topic would also be appreciated. Thanks in advance.
RE: Grouping algorithm - DeaD_EyE - May-19-2020
You can solve it with numpy:
import numpy as np matrix = [ [0, 0, 0, 0, 1], [0, 0, 0, 1, 1], [0, 0, 1, 0, 1], [0, 0, 0, 0, 0], ] group = [index for index, value in np.ndenumerate(matrix) if value == 1]Without numpy:
[(i,j) for i, row in enumerate(matrix) for j, val in enumerate(row) if val == 1]Decomposed:
group = []
for i, row in enumerate(matrix):
for j, val in enumerate(row):
if val == 1:
group.append((i, j))
RE: Grouping algorithm - riccardoob - May-19-2020
(May-19-2020, 10:28 AM)DeaD_EyE Wrote: You can solve it with numpy:
import numpy as np matrix = [ [0, 0, 0, 0, 1], [0, 0, 0, 1, 1], [0, 0, 1, 0, 1], [0, 0, 0, 0, 0], ] group = [index for index, value in np.ndenumerate(matrix) if value == 1]Without numpy:
[(i,j) for i, row in enumerate(matrix) for j, val in enumerate(row) if val == 1]Decomposed:
group = [] for i, row in enumerate(matrix): for j, val in enumerate(row): if val == 1: group.append((i, j))
That is not what I need, in fact my example does not explain my needs well, I'll try and explain it again.
I have this matrix
matrix = [
[0,0,0,1,1,0],
[0,1,1,1,0,0],
[0,0,0,0,0,0],
[1,0,1,0,1,0],
]If the coordinates are coord = (0, 3)the list returned must be
group = [(0, 3), (0, 4), (1, 1), (1, 2), (1, 3)]; the '1' in the last row must be ignored given that they are not adjacent to
(0, 3)nor to any of its adjacent (ora adjacent to adjacent...).
RE: Grouping algorithm - deanhystad - May-19-2020
matrix = [
[0, 0, 0, 0, 1],
[0, 0, 0, 1, 1],
[0, 0, 1, 0, 1],
[0, 0, 0, 0, 0],
]
def get_cells(matrix, r, c):
"""Return list of continuous matches of matrix[r][c]. A continuous
match is if a cell left, right, above or below has the same value.
"""
def check_adjacent(coord, r, c):
# Append (coord[0]+r, coord[1]+c) if equal value
r += coord[0]
c += coord[1]
if 0 <= r < len(matrix) and 0 <= c < len(matrix[0]):
if not (r, c) in coords and matrix[r][c] == value:
coords.append((r, c))
value = matrix[r][c]
coords = [(r, c)]
for coord in coords:
# Look all around for a match. Appending to list used
# for iteration provided an implicit interpolation
check_adjacent(coord,-1,0)
check_adjacent(coord,1, 0)
check_adjacent(coord,0,-1)
check_adjacent(coord,0,1)
return coords
x = get_cells(matrix, 3, 3)
x.sort()
print(x)
RE: Grouping algorithm - riccardoob - May-19-2020
(May-19-2020, 12:07 PM)deanhystad Wrote: matrix = [
[0, 0, 0, 0, 1],
[0, 0, 0, 1, 1],
[0, 0, 1, 0, 1],
[0, 0, 0, 0, 0],
]
def get_cells(matrix, r, c):
"""Return list of continuous matches of matrix[r][c]. A continuous
match is if a cell left, right, above or below has the same value.
"""
def check_adjacent(coord, r, c):
# Append (coord[0]+r, coord[1]+c) if equal value
r += coord[0]
c += coord[1]
if 0 <= r < len(matrix) and 0 <= c < len(matrix[0]):
if not (r, c) in coords and matrix[r][c] == value:
coords.append((r, c))
value = matrix[r][c]
coords = [(r, c)]
for coord in coords:
# Look all around for a match. Appending to list used
# for iteration provided an implicit interpolation
check_adjacent(coord,-1,0)
check_adjacent(coord,1, 0)
check_adjacent(coord,0,-1)
check_adjacent(coord,0,1)
return coords
x = get_cells(matrix, 3, 3)
x.sort()
print(x)I tested that on some cases and it seems to work perfectly, just one little problem: if I want to consider adjacent aven cells that are diagonally connected to each other, how do I have to edit that code?
RE: Grouping algorithm - deanhystad - May-19-2020
Add diagonal checks inside the for loop. You would add a check_adjacent(coord, 1, 1) for example.
RE: Grouping algorithm - riccardoob - May-19-2020
(May-19-2020, 01:11 PM)deanhystad Wrote: Add diagonal checks inside the for loop. You would add a check_adjacent(coord, 1, 1) for example.
Perfect, thank you very much for your answers
RE: Grouping algorithm - deanhystad - May-19-2020
Bad comment in my program. Appending to the list used for iteration provides an implicit recursion. This is a recursive algorithm without an recursive function call.