1

At the moment I've got a set of arrays of elements, say,

[1, 2, 3]
[2, 4]
[5, 6, 7]
[1 , 44]
[5, 12]
etc...

What I want to do is to group these groups into supergroups if they share at least one element together. That is, the arrays above should become:

[1, 2, 3, 4, 44]
[5, 6, 7, 12]

The data I have is much larger and I wonder what is the efficient way of performing such operation.

My guess is take first array, go through all others, if there is intersection, join them and start from the top again, until there is no intersection of first with others. Then follow on to the second one etc...

Is there a better way to do it? I'm especially interested if it could be done easily in PHP, but pseudocode would be good as well..

4

1 に答える 1

0

だから、これは私が思いついた最高のものです：

$j = 0;
while(array_key_exists($j, $groups)){
    $i = $j + 1;

    while(array_key_exists($i, $groups)){
        if(count(array_intersect($groups[$j], $groups[$i])) > 0){
            $groups[$j] = array_merge($groups[$j], $groups[$i]);
            $groups[$j] = array_unique($groups[$j]);
            unset($groups[$i]);
            $i = $j + 1;
            $groups = array_values($groups);
        }
        else{
            $i = $i + 1;
        }
    }

    $j = $j + 1;
}
于 2013-01-01T22:10:02.263 に答える