Как получить множественные пересечения многомерного массива?
Начальное:
Array
(
[0] => Array
(
[0] => a
[1] => b
)
[1] => Array
(
[0] => a
[1] => c
)
[2] => Array
(
[0] => c
[1] => b
)
[3] => Array
(
[0] => d
[1] => e
)
)
Результат:
Array
(
[0] => Array
(
[0] => a
[1] => b
[2] => c
)
[1] => Array
(
[0] => d
[1] => e
)
)
Первые три элемента исходного массива связаны друг с другом, но последний — нет. Я думаю, что это может быть решено с помощью Floyd-Warshall Algoritm. Пожалуйста, помогите мне получить результат.
Решение
Понятия не имею, что такое алгоритм Флойд-Варшалла, и я не уверен в ваших потребностях в оптимизации, но я сделал это:
$array = array(
['a', 'b'],
['a', 'c'],
['c', 'b'],
['d', 'e']
);
$result = array();
foreach($array as $itemOriginal){ //passing every array from the original array
$passed = false;
foreach($result as &$itemResult){ //passing every array from the new array (empty in the start)
foreach($itemOriginal as $item){ //passing every item from original arrays
if(in_array($item, $itemResult)){ //checking if the item is in one of earlier passed array transfered into new array already
$itemResult = array_unique(array_merge($itemResult, $itemOriginal)); //merging items into new array if one of their items equals
$passed = true; //no need to check another item from the current original array
break;
}
}
if($passed == true) //no need to find any of original items in new array
break;
}
if($passed == false) //for case the none of checked original items are in new array
$result[] = $itemOriginal;
}
echo '<pre>';
print_r($result); //to check it
Другие решения
$result = array();
foreach ($array as $item) {
// If we're just getting started, get started
if (count($result) === 0) {
$result[] = $item;
// Otherwise, look for merge opportunities
} else {
$merged = false;
// Loop existing items
foreach ($result as $k => $resultItem) {
// If there's a match, merge & break
if (count(array_intersect($resultItem, $item)) > 0) {
$result[$k] = array_merge($resultItem, $item);
$merged = true;
break;
}
}
// If no match was found, create a new element
if (!$merged) {
$result[] = $item;
}
}
}