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

Question

[un1t]

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

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. И это выполняется очень долго. Хотелось бы получить линейный алгоритм.

Comments

[agmt]

Как я понял, это задача кластеризации/поиска связного графа? Какова мощность множества, подмножествами которого являются перечисленные выше множества?
Если к «Есть набор множеств» добавить «set(10)», то будет ли в результате «set(10)»?

[un1t]

> Как я понял, это задача кластеризации?
Похоже на то.

> Какова мощность множества, подмножествами которого являются перечисленные выше множества?
В среднем числов элементов результирующих множествах 2-5. Можно считать что боллее 10 элементов не бывается.

>Если к «Есть набор множеств» добавить «set(10)», то будет ли в результате «set(10)»?
Да

[agmt]

> В среднем числов элементов результирующих множествах 2-5. Можно считать что боллее 10 элементов не бывается.
Я про то число, которое в итоге выльется в количество вершин графа (см. решение «Mephi1984»), ибо от этого зависит представление графа, а значит и сложность поиска.

[un1t]

Вершин графа в этом случае будет около 2,5 миллионов.

Answer 1

[B@rmaley.e><e]

Обозначим: n — количество множеств, m — суммарное количество элементов во множествах, k — количество уникальных элементов в объединении всех множеств.

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

Мне кажется, предложенный алгоритм является оптимальным: в любом случае нужно рассмотреть каждый элемент каждого множества, что даёт оценку в минимум O(m) операций.

Comments

[un1t]

Идея кажется интересной, но не могли бы вы пояснить.

> Создать k множеств из одного элемента.
соддаем —
set(1), set(2), set(3), set(4), set(5), set(6), set(7), set(8), set(9)
вот только как их дальше использовать?

> Далее проходим по исходным множествам, считая каждое множество запросом на объединение.
> А именно, проходим по элементам множества и объединяем множество, соответствующее
> текущему элементу со множеством, соответствующим предыдущему.

Т.е. первая итерация пробуем объединить set(1, 2) и set(3).

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

[B@rmaley.e><e]

Использовать в соответствии с интерфейсом структуры (опять же см. статью). Она позволяет оперировать с множествами посредством их представителей — элементов этих множеств. По сути, структура умеет выполнять запросы вроде «объединить множество, содержащее x, с множеством, содержащим y». При этом на каждом шаге алгоритма каждый элемент принадлежит только одному множеству (данные множества не имеют ничего общего с исходными множествами!).

Данный подход не зависит от порядка, в котором перебираются исходные множества, т.к. мы лишь вызываем операцию объединения, которая является ассоциативной.

[un1t]

Т.е. вначале мы создаем данную структуру из исходных данных.

make_set(1)
make_set(2)
make_set(3)
make_set(4)
make_set(5)
make_set(6)
make_set(7)
make_set(8)
make_set(9)

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

В результате у нас получается мапка {1: 2, 2: 6, 3: 2, 4: 5, 5: 5, 6: 6, 7: 8, 8: 8, 9: 8}

А как нам из этого получить объединенные множества?

[B@rmaley.e><e]

Для предложенного набора множеств последовательность запросов может быть такой:

for i in [1..9] make_set(i)

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

Результатом будут множества {1,2,3,6}, {4,5}, {7,8,9}. Получить их можно так: пройдёмся по номерам от 1 до k, для каждого номера x вызывая find_set(x) — это будет идентификатор соответствующего множества. Его можно использовать, например, с map'ой, которая по id будет отдавать соответствующее множество.

К слову: предложенный подход полностью аналогичен вариантам с графами. Только здесь граф не строится явно.

[un1t]

Спасибо, теперь все встало на свои места. Осталось только протестировать на реальных данных.

Answer 2

[turboNOMAD]

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

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

Кстати, для работы с графами могу посоветовать соответствующую библиотеку из boost, если подразумевается C++.

Comments

[un1t]

Спасибо.

Answer 3

[Mephi1984]

Вот такая у меня идея.
Из всех множеств берем все числа — получаем N чисел, и сделаем из них граф с N вершинами.
Затем для каждого множества — соединяем вершины. То есть например множество (7,8,9) связывает двумя ребрами три вершины: 7 — 8 — 9.
Затем из полученного графа вычисляем компоненты связности. Википедия пишет, что время выполнения — линейное.

Comments

[agmt]

Да, похоже на правду. Возможно, надо добавить счётчик множеств, чтобы различать [[7,8],[8,9]] и [[7,8,9]], если это требуется условием. А дальше просто пробежаться по всем элементам, у которых этот счётчик >1 и от них уже делать поиск.

[un1t]

Выборка из графа будет линейной. А вот для построения графа похоже, что нужно много времени.

Answer 4

[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. Совместить множества в ответ. Готово.

Не очень линейно, да. Может, натолкнет…