Задача со множествами, помогите решить

Есть набор множеств

set(1, 2)
set(3)
set(4, 5)
set(3, 2, 6)
set(6)
set(7, 8)
set(9, 8)


Нужно объединить все множества которые пересекаются.

Так например set(1, 2) нужно объединить с set(3, 2, 6) и с set(3). Аналогично нужно проделать со всеми множествами.

Результат должен получиться такой:

set(1, 2, 3, 6)
set(4,5)
set(7, 8, 9)


Дополнительные условия.
Количество множеств — 5 миллионов.
Множества выбраны таким образом, что одно множество в среднем объединяется с 1-5 другими множествами. Будем считать, что количество множеств с которым может быть объединено любое множество из этого набора никогда не превышает 10.

Я могу придумать какие-то алгоритмы, но у них всех сложность n^2. И это выполняется очень долго. Хотелось бы получить линейный алгоритм.
  • Вопрос задан
  • 4007 просмотров
Решения вопроса 1
barmaley_exe
@barmaley_exe
Обозначим: n — количество множеств, m — суммарное количество элементов во множествах, k — количество уникальных элементов в объединении всех множеств.

Решение за O(m):
Создать k множеств из одного элемента. Далее проходим по исходным множествам, считая каждое множество запросом на объединение. А именно, проходим по элементам множества и объединяем множество, соответствующее текущему элементу со множеством, соответствующим предыдущему. Чтобы делать это быстро пригодится структура система непересекающихся множеств. Эта структура позволяет выполнять нужные операции в среднем столь быстро, что можно считать их O(1) (хотя, строго говоря, асимптотика там не константная, см. статью).
В результате такого прохода мы обработаем каждый из m элементов один раз, затратив на него ≈O(1) времени. Отсюда получается оценка O(m).
В худшем случае такой алгоритм будет работать за O(n*k) (в каждом множестве можно избавиться от повторов, поэтому элементов в нём будет не более k).

Мне кажется, предложенный алгоритм является оптимальным: в любом случае нужно рассмотреть каждый элемент каждого множества, что даёт оценку в минимум O(m) операций.
Ответ написан
Пригласить эксперта
Ответы на вопрос 3
turboNOMAD
@turboNOMAD
Постройте граф, где каждый элемент — вершина, а ребра обозначают принадлежность к одному множеству. При этом если одну и ту же пару элементов содержат несколько множеств, одного ребра достаточно. Такой граф строится за один проход.

Искомые множества — связные подграфы полученного графа.

Кстати, для работы с графами могу посоветовать соответствующую библиотеку из boost, если подразумевается C++.
Ответ написан
Mephi1984
@Mephi1984
Вот такая у меня идея.
Из всех множеств берем все числа — получаем N чисел, и сделаем из них граф с N вершинами.
Затем для каждого множества — соединяем вершины. То есть например множество (7,8,9) связывает двумя ребрами три вершины: 7 — 8 — 9.
Затем из полученного графа вычисляем компоненты связности. Википедия пишет, что время выполнения — линейное.
Ответ написан
Urvin
@Urvin
1. Выписать уникальные цифры, напротив них поставить индексы множеств.
1 — 0
2 — 0, 3
3 — 1, 3
4 — 2
5 — 2
6 — 3, 4
7 — 5
8 — 5, 6
9 — 6

2. Опустить уникальные цифры, где количество индексов множеств меньше 2
2 — 0, 3
3 — 1, 3
6 — 3, 4
8 — 5, 6

3. Совместить индексы множеств сокращенного списка
0, 3, 1, 4
5,6

4. Узнать индекс пропущенных множеств
2

5. Совместить множества в ответ. Готово.

Не очень линейно, да. Может, натолкнет…
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы