Algorithm for grouping items

[okabe]

Hi everyone, i have some troubles to solve this "grouping" problem.

 

I have 2D (nxn) array and i want to group all related item to groups.

 

Items are considered to be related in 2 cases: when they have the same edge or top.

$table = array(
 array( 0, 0, 0, 0, 0, 0),
 array( 0, 0, 1, 2, 0, 0),
 array( 0, 0, 0, 0, 0, 0),
 array( 0, 3, 0, 4, 0, 0),
 array( 0, 0, 5, 0, 0, 0),
 array( 0, 0, 0, 6, 0, 7)
);

And this is result which i want to achieve :

$groups= array(
 array( 1, 2),
 array( 3, 4, 5, 6),
 array( 7 ),
);

I will be grateful for any help. THX

Edited June 10, 2013 by okabe

[requinix]

Just want an algorithm?

 

Define another array, like $table, that tells you what "group" each cell belongs to. It should eventually end up like

$tablegroups = array(
	array( 0, 0, 0, 0, 0, 0),
	array( 0, 0, 1, 1, 0, 0),
	array( 0, 0, 0, 0, 0, 0),
	array( 0, 2, 0, 2, 0, 0),
	array( 0, 0, 2, 0, 0, 0),
	array( 0, 0, 0, 2, 0, 4) // *
);

Loop through all the rows in $table (first dimension) then the columns (second dimension).

foreach ($table as $r => $row) {
	foreach ($row as $c => $column) {

Skip over empty cells.

 

Look at the previous column (if present) and the three cells above in the previous row (if present) in $tablegroups, ignoring empty cells.

if ($r > 0) {
	if ($c > 0) {
		// look at [$r-1][$c-1]
	}
	// look at [$r-1][$c]
	if ($c < 5) {
		// look at [$r-1][$c + 1]
	}
}
if ($c > 0) {
	// look at [$r][$c - 1]
}

- Assign this cell to the first group you find. Since you're ignoring empty cells and all four possible cells have been examined previously, every cell you find will be in a group

- If there are multiple groups then merge the groups

- If there are no cells/groups then create a new group

- Update $tablegroups for the current cell

 

Now define merging groups:

1. Pick a winning group

2. For each cell in the other groups,

2a. Move it into the winning group

2b. Update $tablegroups accordingly

 

* If getting groups 1, 2, and 4 is a problem (should be 1, 2, 3) then you can renumber the groups at the end

Edited June 10, 2013 by requinix