How to "zero" all entries in an array with an equal adjacent entry?

user_14871424 0
Viewed 106

I have a large array of 1's and 0's. Each time a 1 appears in it, I want to make sure that all the 1's adjacent (or diagonal) to that 1 are set to 0 - so that the array you are left with has one 1 for every "group" of ones that appeared in the original array (I don't mind which 1 is kept per group, just as long as there are no adjacent/neighbouring 1's).

For example, with the following array (much smaller than what I will be dealing with, but I want to illustrate the problem).

[[0. 0. 0. 1.]
[0. 1. 0. 0.]
[0. 1. 0. 0.]
[1. 0. 0. 1.]
[0. 0. 1. 0.]]

I would want to return an array that looks like:

[[0. 0. 0. 1.]
[0. 0. 0. 0.]
[0. 0. 0. 0.]
[1. 0. 0. 0.]
[0. 0. 1. 0.]]

I have tried the following code for the above array (which is labelled as a) in order to achieve this:

# Define a function which finds if an entry has a 1 neighbouring it
def has_neighbour(matrix, x, y):
    if matrix[x-1,y]==1 or matrix[x+1,y]==1 or matrix[x, y+1]==1 or matrix[x, y-1]==1 or matrix[x+1, y+1]==1 or matrix[x+1, y-1]==1 or matrix[x-1, y+1]==1 or matrix[x-1, y-1]==1:

# Find the entries in the matrix of 1 and if they have an adjacent 1, set them to zero
for i in range(4):
    for j in range(3):
        if a[i,j]==0 or (a[i,j] == 1 and has_neighbour(a, i, j)==True):
            a[i,j] = 0
        else:
            a[i,j] = 1

# Re-search along the last row and column for adjacent 1's, setting them to zero where necessary. This is needed due to for loops not changing the last row and column of an array
for i in range(4):
    if a[i,3]==0 or (a[i,3]==1 and (a[i+1,3]==1 or a[i-1,3]==1)):
        a[i,3] = 0
    else:
        a[i,3]=1

for j in range(3):
    if a[4, j]==0 or (a[4, j]==1 and (a[4, j+1]==1 or a[4, j-1]==1)):
        a[4, j] = 0
    else:
        a[4, j] = 1

However, this code returns the following array:

[[0. 0. 0. 1.]
[0. 0. 0. 0.]
[0. 0. 0. 0.]
[0. 0. 0. 1.]
[0. 0. 1. 0.]]

Anyone know what I is going wrong here? I am very confused as it's getting rid of some 1's I don't want it to and not getting rid of some that I do want it to.

Edit @JohnColeman's answer is the closest to working so far. However, it fails on the following matrix (I've attached his code, but changed the test part to the matrix that it is failing with):

def pick_reps(matrix):
    m = len(matrix)
    n = len(matrix[0])
    reps = [[0]*n for _ in range(m)]
    represented = set()
    for i, row in enumerate(matrix):
        for j,x in enumerate(row):
            if x == 1:
                #check if this position is in an already represented block
                covered = False
                if j > 0 and (i,j-1) in represented:
                    covered = True
                elif i > 0 and (i-1,j) in represented:
                    covered = True
                elif i > 0 and j > 0 and (i-1,j-1) in represented:
                    covered = True
                elif i > 0 and j < n and (i-1,j+1) in represented:
                    covered = True
                if not covered:
                    reps[i][j] = 1
                represented.add((i,j))
    return reps

#test:

matrix = [[0, 0, 0, 0],
          [0, 0, 0, 1],
          [0, 1, 1, 0],
          [1, 0, 1, 1],
          [0, 0, 0, 1]]

reps = pick_reps(matrix)
for row in reps: print(row)

This should return a matrix with only one 1 in it. However, it returns:

[[0, 0, 0, 0],
 [0, 0, 0, 1],
 [0, 1, 0, 0],
 [0, 0, 0, 0],
 [0, 0, 0, 0]]
arrays python
2 Answers

I think your is_neighbo(u)r1 function still needs some work. There is a lot of logic down the line that should in fact be part of that function; in particular, the borderline cases should be accounted for inside the function. Here's one way to implement your idea:

def has_neighbor(matrix, x, y):
    """Return True if any of the neighboring cells are equal to 1"""
    
    # just in case you need to change this value at some point
    value = 1 
    
    # Define neighbors to check
    corners = [(-1, -1),
               (0, -1),
               (1, -1),
               (1, 0),
               (1, 1),
               (0, 1),
               (-1, 1),
               (-1, 0)]
    
    # get the boundaries of the matrix
    x_max, y_max = matrix.shape
    
    # for each neighbor
    for x_off, y_off in corners:
        
        # get the new coordinates to check
        x2 = x+x_off
        y2 = y+y_off
        
        # skip coordinates that are out of bounds
        out_of_grid = [x2 < 0,
                       y2 < 0, 
                       x2 >= x_max, 
                       y2 >= y_max]
        
        if any(out_of_grid):
            continue
        
        # finally!
        if matrix[x2, y2] == value:
            return True

It can now handle the borderline cases, which makes the final loop much simpler:

x_max, y_max = a.shape

for x in range(x_max):
    for y in range(y_max):
        if has_neighbor(a, x, y):
            a[x, y] = 0

The output is as desired:

array([[0, 0, 0, 1],
       [0, 0, 0, 0],
       [0, 0, 0, 0],
       [1, 0, 0, 0],
       [0, 0, 1, 0]])

1 NB: In code, American spelling is more common.

user_158730430

This probably isn't very idiomatic, but you could iterate through the array - when you find a 1 you call a recursive function to clear all reachable 1s. This of course will clear the initial, representative element, so you set that back to 1.

a = [[0, 0, 0, 1],
    [0, 1, 0, 0],
    [0, 1, 0, 0],
    [1, 0, 0, 1],
    [0, 0, 1, 0]]
          
def clear(a, r, c):
    if r < 0 or r == len(a) or c < 0 or c == len(a[0]) or a[r][c] == 0:
        return
    
    a[r][c] = 0
    for i in [-1, 0, 1]:
        for j in [-1, 0, 1]:
            clear(a, r+i, c+j)
                
for r in range(len(a)):
    for c in range(len(a[0])):
        if a[r][c] == 1:
            clear(a, r, c)
            a[r][c] = 1
            
for row in a: print(row)

Output:

[0, 0, 0, 1]
[0, 1, 0, 0]
[0, 0, 0, 0]
[0, 0, 0, 1]
[0, 0, 0, 0]
user_64388190
Related