PHP элементов быстрой кластеризации, хранящиеся в массиве

Question

У меня есть массив, состоящий из 1,5 миллионов пара элементов (разделенный ' «):

$array { 
    [0] => "element1 element2" 
    [1] => "element2 element3" 
    [2] => "element8 element4" 
    [3] => "element8 element5" 
    [4] => "element4 element5" 
    [5] => "element6 element7" 
    [6] => ... 
}  

Каждая пара элемента является уникальной, и элементы представляют собой строки от 15 до 20 символов.

В моем конвейере этот массив означает [0] «элемент1 связан с элементом2», [1] «элемент2 связан с элементом3», ... Я хотел бы объединить все связанные элементы и получить вывод похожие на:

$array_output { 
     [0] => "element1 element2 element3" 
     [1] => "element8 element4 element5" 
     [2] => "element6 element7" 
     [3] => ... 
} 

Я думаю, эта задача очень проста, и я, вероятно, отсутствует очевидный способ сделать это, но я не нашел быстрый способ группироваться мои элементы (т.е. от нескольких минут до нескольких несколько часов).

Answer 1

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

Чтобы сделать это в PHP:

1. Преобразование входных данных для многомерного массива ([["element1", "element2"],["element2","element3"]] и т.д.)
2. Инициализируют список узлов в представлении карты с каждым узлом, указывая на множество, содержащее только этот узел (например, ["element1" => ["element1"],"element2" => ["element2"]] и т. д.)
3. Для каждого спаривания в массиве из (1) объедините множества из двух элементов в массиве из (2) и укажите оба элемента, а также любые другие элементы в наборе, чтобы вновь объединенный комплект
4. Поместите все наборы из (3) в виде набора (наборов), так что вы получите каждый только один раз
5. Преобразование каждого набора в нужный формат вывода

Вы хотите использовать ссылочный оператор (&), чтобы повторно использовать те же массивы в (3). Алгоритм будет намного проще реализовать на Java или что-то более очевидное hashmaps и hashtables.