PHP嵌套数组'网格状'分组

Question

I'm having a few issues writing accurate and efficient code in PHP for this problem below.

I have a list of users, and each user has a list of friends. I want to group all the friends into groups where each person has at least one friend with another user.

Below is a simplified array, with unneeded array keys removed and user id's replaced with names.

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

The output of this should be as follows:

Group 1: Sarah, Frank, Bob, Jane, Ted

Group 2: John, Peter, Sam

Group 3: Sally, Kevin

As a note, there is no data for Jane, but Sarah is friends with her so this grouping can happen. Also There will be users with no friends, they should be placed in there own group.

I have tried to write code for this, but it is very inefficient and contains three nested foreach loops. I am quite ashamed :(

$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

A pretty simple and probably not optimal solution would be to flatten the input array first into an array of 1-dimensional arrays. You only need to know which initial groups have matching friends so you know which groups to merge with each other.

Flattening your example input array would result in:

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
        )

)

You can use array_intersect to check for matching friends for each group and a combination of array_unique and array_merge to merge two groups.

Here's an example of this approach:

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>';

This is the output for the example data:

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
        )

)