Jump to content

Algorithm for grouping items


okabe

Recommended Posts

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 by okabe
Link to comment
Share on other sites

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 by requinix
Link to comment
Share on other sites

This thread is more than a year old. Please don't revive it unless you have something important to add.

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Restore formatting

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×
×
  • Create New...

Important Information

We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.