Resolved Grouping values in matrix

[Oking]

I have a 2d array(5x6 matrix) and have objects in each location. Some objects are empty others have values. I need to scan the array and group the objects with values if they are next to, on top or on bottom of. Could be one big object or many if the objects are scattered. Suggestions?

 

[Skydiver]

There are well researched algorithms for form fitting and bin packing. Some of the classic ones are used for attacking pentominos and Tetris problems.

The added degree of freedom of being able to change the pieces shapes makes things interesting. One approach could be to apply standard algorithms. If solution found, obviously stop. If not, permute the shape(s) then try again.

 

[JohnH]

Suggestion for algorithm is to start with a 2D array of 0/1, iterate it and if there is a 1 determine group by looking at adjacent left or top, assign if apply (!=0), if none apply increment group number and assign that. You have to backtrack to merge groups if adjacent left and top conflict.

 

[Skydiver]

Yes, basically a flood fill algorithm where you are flood filling the group members.

So I must have misinterpreted what the OP was asking for. I thought that the OP wanted to create groups of certain membership counts, hence my heading towards algorithms for layout and bin packing. If all the OP is asking for is to find existing groups, then a simple scan and flood fill should work to identify the groups.

 

[Skydiver]

Stumbled across this. I've not looked too deeply at the details of their implementation though, so take it with a huge grain of salt. I'll just say that another algorithm they had for solving a different problem had great value as a teaching aid, but not as much value as a production ready solution (e.g not memory or CPU efficient).

Count number of islands | Techie Delight

Given a binary matrix where 0 represents water and 1 represents land, and connected ones form an island, count the total islands.

www.techiedelight.com

 

[Oking]

Thanks everyone for your input! I had a late night vision and put it to work this morning. I backed up to where I was scanning the matrix for the row/col values and created the groups there using the rows and column numbers + or - 1 as needed. Before I was clearing the row, col list as I was adding it which didnt give me the opportunity to compare the next value to the values already in the list. So now I can loop through the row/col list as I come to the next location and see if the value matches any of those as well.