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?

 

[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?

As an example
11000
11000
11000
00100
00100
00000

Now create 2 groups with the ones. Group1 has 6 values group2 has 2. The locations will change though.

 

[Oking]

Also I scanned the array and have the row/column values of all the objects with value. Every thing I try doesn’t always get all the objects in the group correctly.

 

[Skydiver]

Show us your code. Post it was text in code tags. Never as a screenshot.

 

[Oking]

public List<Pod> createNewGroup()
        {
            try
            {
                groupPods = new List<Pod>();
                int row, col, oldRow, oldCol;
                groupPods.Clear();
                row = podRow[0];
                col = podCol[0];
                oldRow = row;
                oldCol = col;
                groupPods.Add(matrix[podRow[0], podCol[0]]);
                podRow.RemoveAt(0);
                podCol.RemoveAt(0);
                for (int i = 0; i < podRow.Count; i++)
                {
                    if (podRow == row)
                    {
                        if (podCol == podCol[0])
                        {
                            CrestronConsole.PrintLine("Found {0}, {1}", podRow[0], podCol[0]);
                            groupPods.Add(matrix[podRow, podCol]);
                            row = podRow;
                            podRow.RemoveAt(i);
                            podCol.RemoveAt(i);
                            i = 0;
                        }
                        else
                        {
                            row = oldRow;
                        }
                    }
                    if (podCol == col)
                    {
                        if (podRow == podRow[0])
                        {
                            groupPods.Add(matrix[podRow, podCol]);
                            col = podCol;
                            podRow.RemoveAt(i);
                            podCol.RemoveAt(i);
                            i = 0;
                        }
                        else
                        {
                            col = oldCol;
                        }
                    }
                }                
            }
            catch (Exception e)
            {
                CrestronConsole.PrintLine("Error in matrix search {0}", e.Message);
            }

            return groupPods;
        }

This is one of the many ways I have tried..

 

[Oking]

for (int i = 0; i < 5; i++)
            {
                for (int j = 0; j < 6; j++)
                {
                    if (matrix[i, j].PodLoc.Length > 0)
                    {
                        podRow.Add(i);
                        podCol.Add(j);
                    }
                }
            }   //Get int values of their location

This is where I am scanning the matrix for the locations that have value. (This works fine)

 

[Skydiver]

Please use code tags when posting code. That's the toolbar icon that looks like </>. I'll try to fix your past posts...

 

[Skydiver]

The elements of the matrix always 1's and 0's?

Are there any rules on the shape a group can take?

Are there any rules on how close the groups can be to each other?

 

[Oking]

The objects actually have string values in them I was just giving a visual view of the matrix. There’s no rules on the shape just above, below or on the side. No rules on how close they will be just new groups won’t be right next to other group.

 

[Oking]

The objects actually have string values in them I was just giving a visual view of the matrix. There’s no rules on the shape just above, below or on the side. No rules on how close they will be just new groups won’t be right next to other group.

Also one of the strings in the objects is the location name. The names are A1-A6 first row then B1-B6 second row and so on to E6. I figured the matrix might be easier but we do know the position by the name.

 

[Skydiver]

So this is perfecty valid 2 groups of 1. Group1 has 6 values and Group2 has 2 values.

00000
11100
10000
10100
10100
00000

 

[Oking]

So this is perfecty valid 2 groups of 1. Group1 has 6 values and Group2 has 2 values.

00000
11100
10000
10100
10100
00000

Correct

 

[jmcilhinney]

This is an intriguing problem. The approach that first comes to mind for me would be to create a dummy matrix of bool values, with true representing an element that is set in the original and false representing one that is not. I would then traverse that dummy matrix using nested for loops. Each time I encounter a true element, I would kick off a recursive, breadth-first search to find neighbouring elements that are set. That search would return a list containing the elements in that group. Each time I finished with an element in the inner search, I would reset it, so it will then no be found again in the outer search. I might throw something together to this effect later today.

 

[Skydiver]

Damn this post anesthesia memory loss plus chemo brain. There is an outline of how to lay out things in Skiena's The Algorithm Handbook as well as references to some well regarded libraries that implement them. I can't for the life of me remember right now the problem space name so you can jump to the right chapter. Bin packing in 2D is the only thing that comes to mind.

What makes this problem interesting is that most of the standard algorithms deal with fixed shape objects. Here you have the option to change the shape.

 

[Oking]

When I first posted it I thought someone would say oh that’s easy. I guess I feel a little better now. The first time I built my for loop checking the values it worked but then I shifted the objects and it failed. Driving me mad every time I get it to work I can make it fail.