How could you rewrite a list of lists so that "islands" of values are unique from one another?

Question

Let's say I've got a list of lists (or more conceptually accurate a 2D array):

list = [[1,1,0,0,0],
        [1,1,2,0,0],
        [0,2,2,2,0],
        [0,0,0,2,0],
        [0,0,0,1,0]]

I'd like to identify the different regions of identical values and rewrite the list so that each region has a unique value, like so:

list = [[1,1,2,2,2],
        [1,1,3,2,2],
        [0,3,3,3,2],
        [0,0,0,3,2],
        [0,0,0,4,2]]

I've mostly tried writing variations of a loop parsing the array per value and setting adjacent values equal to each other (which yea, is redundant I guess), BUT ensuring that island of 1s in the top left is distinct from the 1 in the bottom right was just not working. My attempts were spotty at best and non-functional at worst. Examples:

for x in list_length:
     for y in sublist_length:
          try:
               if list[x][y] == list[x+1][y]:
                    list[x+1][y] = list[x][y]
          except:
               pass

or

 predetermined_unique_value = 0

 for x in list_length:
     for y in sublist_length:
          try:
               if list[x][y] == list[x+1][y]:
                    list[x+1][y] = predetermined_unique_value
                    predetermined_unique_value += 1
          except:
               pass

and many slight variations on which directions (up, down, left, right from current spot/point) to check, brute forcing the loop by running it until all spots had been assigned a new value, etc.

Clearly I am missing something here. I suspect the answer is actually super simple, but I can't seem to find anything on google or reddit, or other answers here (I'm probably just conceptualizing it weirdly so searching for the wrong thing).

Just to reiterate, how could you parse that list of lists to organize values into adjacent regions based on identical data and rewrite it to ensure that those regions all have unique values? (I.E. so that there is only one region of the 0 value, one region of the 1 value, etc. etc.)

I hope this is enough information to help you help me, but in truth I just as much am not sure how to do this as I am doing it wrong. Please don't hesitate to ask for more.

Answer 1

You can use skimage.measure.label:

>>> import numpy as np
>>> from skimage import measure
>>>
>>> a = np.array([[1,1,0,0,0],
        [1,1,2,0,0],
        [0,2,2,2,0],
        [0,0,0,2,0],
        [0,0,0,1,0]])
>>> measure.label(a, background=a.max()+1)
array([[1, 1, 2, 2, 2],
       [1, 1, 3, 2, 2],
       [4, 3, 3, 3, 2],
       [4, 4, 4, 3, 2],
       [4, 4, 4, 5, 2]])

Note that the label function has an argument connectivity which determines how blobs/clusters are identified. The default for a 2D array is to consider diagonal neighbors. If that is undesired, connectivity=1 will consider only horizontal/vertical neighbors.

Answer 2

Based on this answer you can do it with ndimage from the scipy library. I applied your data to his answer and that's what I got as result:

from scipy import ndimage
import numpy as np

data_tup = ((1,1,0,0,0),
        (1,1,2,0,0),
        (0,2,2,2,0),
        (0,0,0,2,0),
        (0,0,0,1,0))

data_list = [[1,1,0,0,0],
        [1,1,2,0,0],
        [0,2,2,2,0],
        [0,0,0,2,0],
        [0,0,0,1,0]]

def find_clusters(array):
    clustered = np.empty_like(array)
    unique_vals = np.unique(array)
    cluster_count = 0
    for val in unique_vals:
        labelling, label_count = ndimage.label(array == val)
        for k in range(1, label_count + 1):
            clustered[labelling == k] = cluster_count
            cluster_count += 1
    return clustered, cluster_count

clusters, cluster_count = find_clusters(data_list)
clusters_tup, cluster_count_tup = find_clusters(data_tup)
print(" With list of lists, Found {} clusters:".format(cluster_count))
print(clusters, '\n')

print(" With tuples of tuple, Found {} clusters:".format(cluster_count_tup))
print(clusters_tup)

Output:

 With list of lists, Found 5 clusters:
[[2 2 0 0 0]
 [2 2 4 0 0]
 [1 4 4 4 0]
 [1 1 1 4 0]
 [1 1 1 3 0]] 

 With tuples of tuple, Found 5 clusters:
[[2 2 0 0 0]
 [2 2 4 0 0]
 [1 4 4 4 0]
 [1 1 1 4 0]
 [1 1 1 3 0]]

Both times the Output is a list of list. If you wish to have it different, the function needs to be changed inside.

Answer 3

I'm not sure how good the performance of this solution is but here's a recursive approach to identify a connected segment. It will take a coordinate and return the same list of islands with every coordinate that was part of the same island as the given coordinate with True.

islands = [[1,1,0,0,0],
        [1,1,2,0,0],
        [0,2,2,2,0],
        [0,0,0,2,0],
        [0,0,0,0,0]]

def print_islands():
        for row in islands:
                print(row)

def get_bool_map(i, j):
        checked_indexes = [[False] * len(islands[0]) ] * len(islands) 
        checked_cords = []
        def check_island_indexes(island_value, m, i, j):
                if i < 0 or j < 0:
                        return
                try:
                        if m[i][j] != island_value:
                                return
                        else:
                                if [i, j] in checked_cords:
                                        return
                                else:
                                        checked_cords.append([i, j])
                                m[i][j] = True
                except IndexError:
                        return
                check_island_indexes(island_value, m, i - 1, j)
                check_island_indexes(island_value, m, i + 1, j)
                check_island_indexes(island_value, m, i, j - 1)
                check_island_indexes(island_value, m, i, j + 1)
        check_island_indexes(islands[i][j], islands, i, j)

get_bool_map(0, 4)
print_islands()

[1, 1, True, True, True]
[1, 1, 2, True, True]
[0, 2, 2, 2, True]
[0, 0, 0, 2, True]
[0, 0, 0, 1, True]