Группировка пар

[Алексей3]

Всем добра!

Есть пары, пусть, например: (А, Б) (А, В) (А, Г) (В, Г) (А, Д) (Д, В)
Нужно элементы из этих пар сгруппировать в одну или несколько групп так, чтобы взяв из любой группы пару любых элементов, они нашлись в одной исходной паре. Порядок элементов в парах и группах значения не имеет.

То есть в итоге должно получиться: (А, В, Г) (А, В, Д) (А, Б)
То есть если из первой группы (А, В, Г) взять, например В и Г, то пара (В, Г) была в исходных. (А, Г) тоже есть, и (А, В) есть в исходных.

Вот, собственно и вопрос, какой алгоритм решения этой задачи?

 

[hell0w0rd]

Надо гуглить на тему пересечения множеств... Думаю хороший алгоритм будет это решать как-то через графы.
А это вы где такую задачку взяли?

 

[Алексей3]

Пришла при работе над проектом.
Нужно отобрать данные, которые между собой связаны.

 

[hell0w0rd]

хм.. мы же тут не математическую задачку решаем, в таком случае. Можно хоть сколько-то приблизить к реальности задачу?

 

[Алексей3]

Да, на самом деле это и есть реальность, чистая математика. Пришли тексты, у каждого свой номер и номера текстов на него похожих. Нужно сгруппировать, собрав вместе документы, которые похожи каждый на каждого.

 

[keltanas]

http://habrahabr.ru/post/210288/#comment_7243586

похожи каждый на каждого

так они по какому-то признаку должны быть похожи? если тексты 2, 3, 4 похожи на текст №1, может ли это значить, что они похожи между собой?

 

[Алексей3]

Нет, должно быть явное указание, что (2 похоже на 3), (2 на 4) и (3 на 4).

 

[keltanas]

Ну реши перебором, с отходом назад. Но, если текстов много, можно посадить печень.

 

[Алексей3]

Ну, конкретно на данный момент, 4000 текстов и 1 500 000 пар связей.

 

[hell0w0rd]

Есть такая штука - графовые базы данных. Возможно это тот случай.

 

[Дмитрий Пленкин]

Наверное, уже не очень актуально, но все-таки отвечу.

В общем виде задача решается так: http://ru.wikipedia.org/wiki/Алгоритм_Брона_—_Кербоша

Ну и очевидное замечание: если задача стоит как "найти все статьи похожие на статью X", то не нужно перефигачивать все 4000 статей, а достаточно выдернуть из БД (делается это 1-2 запросами):
а) пары, в которые входит текущая статья;
б) пары, образованные элементами из пар, найденных в пункте "а".
И искать группы только среди найденного.