PHPネストされた配列 'メッシュのような'グループ化

Question

私は以下のこの問題のために、PHPで正確で効率的なコードを書いているいくつかの問題があります。

私はユーザーのリストを持っており、各ユーザーには友人のリストがあります。私はすべての友人をグループに分けて、それぞれの人に少なくとも1人の友人が他のユーザーと一緒にいるグループにしたいと思います。

以下は、不要な配列キーが削除され、ユーザーIDが名前に置き換えられた単純化された配列です。

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：サリー、ケビン

メモとして、ジェーンのためのデータはありませんが、サラは彼女と友人ですので、このグループ化が起こる可能性があります。また、友人がいないユーザーもいれば、グループ内に配置する必要があります。

私はこれのためのコードを書こうとしましたが、非常に非効率的で、3つのネストされたforeachループが含まれています。 私はかなり単純で、おそらくない最適解が最初の1次元配列の配列に入力配列をフラット化することです。あなたが唯一のマッチングを持つ最初のどのグループを知る必要があり

$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

:(かなり恥ずかしいですあなたので、友人同士が合併するグループを知っている

しまうあなたの例の入力配列を平坦化して：あなたは、それぞれの友人に一致するかどうかを確認するために使用することができますarray_intersect

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 
     ) 

) 

groupと2つのグループをマージする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 
     ) 

)