PHP Вложенный массив «Mesh Like» Группировка

Question

У меня возникли проблемы с написанием точного и эффективного кода в PHP для этой проблемы ниже.

У меня есть список пользователей, и у каждого пользователя есть список друзей. Я хочу сгруппировать всех друзей в группы, где каждый человек имеет по крайней мере одного друга с другим пользователем.

Ниже приведен упрощенный массив с удаленными ключами из массива и идентификаторы пользователя заменены именами.

Array 

    [Ted] => Array 
     [friends] => Array 
        [0] => Sarah 

    [John] => Array 
      [friends] => Array 
        [0] => Peter 
        [1] => Sam 

    [Peter] => Array 
      [friends] => Array 
        [0] => John 
        [1] => Sam 

    [Frank] => Array 
      [friends] => Array 
        [0] => Bob 
        [1] => Sarah 

    [Kevin] => Array 
      [friends] => Array 
        [0] => Sally 

    [Sam] => Array 
      [friends] => Array 
        [0] => John 
        [1] => Peter 

    [Bob] => Array 
      [friends] => Array 
        [0] => Frank 
        [1] => Sarah 

    [Sarah] => Array 
      [friends] => Array 
        [0] => Frank 
        [1] => Bob 
        [2] => Ted 
        [3] => Jane 

    [Sally] => Array 
      [friends] => Array 
        [0] => Kevin 

    [Jane] => Array 
      [friends] => Array 

Выход из этого должно быть следующим:

Группа 1: Сара, Фрэнк, Боб, Джейн, Тед

Группа 2: Джон, Питер, Сэм

Группа 3: Салли, Кевин

Как примечание, для Джейн нет данных, но Сара дружит с ней, поэтому такая группировка может случиться. Также будут пользователи без друзей, они должны быть размещены в собственной группе.

Я попытался написать код для этого, но он очень неэффективен и содержит три вложенных петли foreach. Я очень стыдно :(

$friendGroups = []; 


foreach($userdata as $key => $user) 
{ 
    $friends = $user["friends"]; 

    // Loop the current groups 
    foreach($friendGroups as $friendkey => $friendValue) 
    { 
     // Does the group contain any of the friends? 
     foreach($friends as $friendID) 
     { 
      if (array_key_exists($friendID, $friendValue)) 
      { 
       // add the friends to this group 
       foreach($friends as $friendIDx) 
       { 
        $friendGroups[$friendkey][$friendIDx] = $userdata[$friendIDx]; 
       } 
       continue 3; 
      } 
     } 
    } 

    $groupID = count($friendGroups); 
    // Create a new group 
    foreach($friends as $friendID) 
    { 
     $friendGroups[$groupID][$friendID] = $userdata[$friendID]; 
    } 
} 

Answer 1

довольно простой и, вероятно, не является оптимальным решением было бы сгладить массив ввода первого в массив 1-мерных массивов. Вам нужно только знать, какие начальные группы имеют согласование друзья, чтобы вы знали, какие группы сливаются друг с другим

Сведения вашего входного массива примера приведут к:.

Array 
(
    [0] => Array 
     (
      [0] => Ted 
      [1] => Sarah 
     ) 

    [1] => Array 
     (
      [0] => John 
      [1] => Peter 
      [2] => Sam 
     ) 

    [2] => Array 
     (
      [0] => Peter 
      [1] => John 
      [2] => Sam 
     ) 

    [3] => Array 
     (
      [0] => Frank 
      [1] => Bob 
      [2] => Sarah 
     ) 

    [4] => Array 
     (
      [0] => Kevin 
      [1] => Sally 
     ) 

    [5] => Array 
     (
      [0] => Sam 
      [1] => John 
      [2] => Peter 
     ) 

    [6] => Array 
     (
      [0] => Bob 
      [1] => Frank 
      [2] => Sarah 
     ) 

    [7] => Array 
     (
      [0] => Sarah 
      [1] => Frank 
      [2] => Bob 
      [3] => Ted 
      [4] => Jane 
     ) 

    [8] => Array 
     (
      [0] => Sally 
      [1] => Kevin 
     ) 

    [9] => Array 
     (
      [0] => Jane 
     ) 

) 

Вы можете использовать array_intersect для проверки соответствия друзей для каждого группу и комбинацию array_unique и array_merge для объединения двух групп.

Вот пример такого подхода:

function flatten($input) { 
    $output = []; 

    $i = 0; 
    foreach ($input as $name => $data) { 
     $output[$i] = [$name]; 
     foreach ($data['friends'] as $friend) { 
      $output[$i][] = $friend; 
     } 

     $i++; 
    } 

    return $output; 
} 

$input = [ 
    'Ted' => [ 
     'friends' => [ 
      'Sarah' 
     ] 
    ], 

    'John' => [ 
     'friends' => [ 
      'Peter', 
      'Sam' 
     ] 
    ], 

    'Peter' => [ 
     'friends' => [ 
      'John', 
      'Sam' 
     ] 
    ], 

    'Frank' => [ 
     'friends' => [ 
      'Bob', 
      'Sarah' 
     ] 
    ], 

    'Kevin' => [ 
     'friends' => [ 
      'Sally' 
     ] 
    ], 

    'Sam' => [ 
     'friends' => [ 
      'John', 
      'Peter' 
     ] 
    ], 

    'Bob' => [ 
     'friends' => [ 
      'Frank', 
      'Sarah' 
     ] 
    ], 

    'Sarah' => [ 
     'friends' => [ 
      'Frank', 
      'Bob', 
      'Ted', 
      'Jane' 
     ] 
    ], 

    'Sally' => [ 
     'friends' => [ 
      'Kevin' 
     ] 
    ], 

    'Jane' => [ 
     'friends' => [] 
    ] 
]; 

$flattened = flatten($input); 

for ($i = 0; $i < count($flattened); $i++) { 
    $mergedIndices = []; 
    // Check for same friends among other groups than current one 
    for ($j = 0; $j < count($flattened); $j++) { 
     if ($i !== $j && count(array_intersect($flattened[$i], $flattened[$j])) > 0) { 
      // Found match between two groups, so merge them 
      $flattened[$i] = array_unique(array_merge($flattened[$i], $flattened[$j])); 
      $mergedIndices[] = $j; 
     } 
    } 

    // Purge merged items 
    foreach ($mergedIndices as $m) { 
     unset($flattened[$m]); 
    } 

    // Re-index array after purging 
    $flattened = array_values($flattened); 
} 

echo '<pre>' . print_r($flattened, 1) . '</pre>'; 

Это выход для примера данные:

Array 
(
    [0] => Array 
     (
      [0] => Ted 
      [1] => Sarah 
      [2] => Frank 
      [3] => Bob 
      [4] => Jane 
     ) 

    [1] => Array 
     (
      [0] => John 
      [1] => Peter 
      [2] => Sam 
     ) 

    [2] => Array 
     (
      [0] => Kevin 
      [1] => Sally 
     ) 

)