Count Number Of Occurence in 2D Array

Question

Let's say I have an array like this

grid: 
    [[1, 1, 0, 0, 0],
    [1, 1, 0, 0, 0],
    [0, 0, 1, 0, 0],
    [0, 0, 0, 1, 1]]

I want to isolate the group of "items" in this case 1's which are three groups the rule being the 0's are used to separate them like intersections. So this example has 3 groups of 1.

If you know how to do this with python, the first question I'd be asked is what I've tried as proof of not handing my homework to the community, the idea I had was to iterate down and left but that would have a high likelihood of missing some numbers since if you think about it, it would form a cross eminating from the top left and well this group is here to learn. So for me and others who have an interest in this data science like problem be considerate.

If you think of the 2D array like a grid, you can iterate over it like you read a book. Top-to-bottom, left-to-right. You can do this with 2 nested "for" loops. — byxor
– byxor, Commented Oct 22, 2019 at 16:25
There are various algorithms developed for this problem, most of which are relatively straightforward to implement. See connected component labeling — jodag
– jodag, Commented Oct 22, 2019 at 16:33
@byxor knowing that the group you saw in the first line (2 numbers) is part of that in the second line is the tricky part. Plus now using that logic to know that group has been done and add to a total number — Sam B.
– Sam B., Commented Oct 22, 2019 at 16:34

crookedleaf · Accepted Answer · 2019-10-22 16:36:10Z

1

If you do not need to know which sets are duplicates, you can use python's set built-in to determine unique items in a list. This can be a bit tricky since set doesn't work on a list of lists. However, you can convert this to a list of tuples, put those back in a list, and then get the len of that list to find out how many unique value sets there are.

grid = [[1, 1, 0, 0, 0],
        [1, 1, 0, 0, 0],
        [0, 0, 1, 0, 0],
        [0, 0, 0, 1, 1]]

unique = [list(x) for x in set(tuple(x) for x in grid)]

unique_count = len(unique)  # this will return 3

answered Oct 22, 2019 at 16:36

crookedleaf

2,2074 gold badges19 silver badges40 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

jodag Over a year ago

are cases like [[1,1,1][1,0,1],[1,1,1]] being ruled out? Or [[1,1,0],[0,1,1]]?

crookedleaf Over a year ago

That would return a value of 2. Python's built-in set when used this way essentially removes all duplicate items from a list. since [1,1,1] is in that list twice, it removes one instance and only keeps the other.

jodag Over a year ago

But my understanding of the problem would be that OP wants it to return 1 since they are all "touching".

crookedleaf Over a year ago

maybe i misunderstood what he is actually trying to do then. he wasn't very clear on what the end result was, so i was going off him saying "I want to isolate the group of 'items' [...] So this example has 3 groups of 1."

crookedleaf Over a year ago

@samuel m can you clarify?

jodag · Accepted Answer · 2019-10-22 17:17:57Z

Relatively straightforward depth first search based implementation of connected component labeling.

def get_components(grid, indicator=1):
    def label(g, row, col, group):
        if row >= 0 and col >= 0 and row < len(g) and col < len(g[row]) and g[row][col] == -1:
            # only label if currently unlabeled
            g[row][col] = group
            # attempt to label neighbors with same label
            label(g, row + 1, col, group)
            label(g, row, col + 1, group)
            label(g, row - 1, col, group)
            label(g, row, col - 1, group)
            return True
        else:
            return False

    # initialize label grid as -1 for entries that need labeled
    label_grid = [[-1 if gc == indicator else 0 for gc in gr] for gr in grid]
    group_count = 0
    for row, grid_row in enumerate(grid):
        for col in range(len(grid_row)):
            if label(label_grid, row, col, group_count + 1):
                group_count += 1
    return label_grid, group_count

The results of label_grid, group_count = get_components(grid) for your example inputs are

label_grid = [[1, 1, 0, 0, 0],
              [1, 1, 0, 0, 0],
              [0, 0, 2, 0, 0],
              [0, 0, 0, 3, 3]]
group_count = 3

And for cases like the following

grid = [[1 0 1],
        [1 1 1]]

we get group_count = 1.

Collectives™ on Stack Overflow

Count Number Of Occurence in 2D Array

2 Answers 2

5 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

5 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related