Grouping algorithm

[riccardoob]

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.

[DeaD_EyE]

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

[riccardoob]

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

[deanhystad]

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)

[riccardoob]

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?

[deanhystad]

Add diagonal checks inside the for loop. You would add a check_adjacent(coord, 1, 1) for example.

[riccardoob]

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

[deanhystad]

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.