Разделить список наборов по общим элементам

Question

Вот суть проблемы: приведен список наборов, например:

[ (1,2,3), (5,2,6), (7,8,9), (6,12,13), (21,8,34), (19,20) ]

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

[ [ (1,2,3), (5,2,6), (6,12,13) ], [ (7,8,9), (21,8,34) ], [ (19,20) ] ]

Обратите внимание на залипание - множество (6,12,13) ​​не имеет общего элемента с (1,2,3), но они попадают в одну группу из-за (5,2,6).

Чтобы усложнить ситуацию, я должен отметить, что у меня нет этих аккуратных наборов, а есть таблица БД с несколькими миллионами строк, которая выглядит следующим образом:

element | set_id
----------------
1       | 1
2       | 1
3       | 1
5       | 2
2       | 2
6       | 2

и т. Д. Поэтому мне бы хотелось, чтобы это делалось в SQL, но я был бы рад общему руководству для решения.

EDIT : Изменены имена столбцов таблицы на (element, set_id) вместо (key, group_id), чтобы сделать термины более согласованными. Обратите внимание, что в ответе Кева используются старые имена столбцов.

Answer 1

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

• для всех i = 1 до N, выполните:
• если я был помечен каким-то j остальное флуд_из (i, i)

где flood_from (i, j) будет определено как

• для каждого набора S, содержащего i, если он еще не помечен j, то:
• пометить S с помощью j и для каждого элемента k из S, если k еще не помечено с помощью j, то пометить его с помощью j и вызвать flood_from (k, j)

Теги наборов дают вам нужные вам подключенные компоненты.

---

В терминах баз данных алгоритм может быть выражен следующим образом: вы добавляете столбец TAG в свою базу данных и вычисляете связанный компонент набора i, выполняя

• S = выбрать все строки, где set_id == i
• установить TAG на i для строк в S
• S '= выбрать все строки, где TAG не установлен и где элемент находится в элементе (S)
• пока S 'не пусто, сделайте
• ---- установите TAG в i для строк в S '
• ---- S '' = выбрать все строки, где TAG не установлен и где элемент находится в элементе (S ')
• ---- S = S union S '
• ---- S '= S' '
• return set_id (S)

---

Другим (теоретическим) способом представления этого алгоритма было бы сказать, что вы ищете фиксированные точки отображения:

• если A = {A ₁ , ..., A _n } является набором множеств, определите union (A) = A ₁ union ... союз A _n
• , если K = {k ₁ , ..., k _p } - это набор целых чисел, определить случаи (K) = набор множеств, пересекающих K

Тогда, если S является множеством, связная компонента S получается путем итерации (инцидентов) o (объединения) на S, пока не будет достигнута фиксированная точка:

1. K = S
2. K '= инциденты (объединение (K)).
3. если K == K ', вернуть K, иначе K = K' и перейти к 2.

Answer 2

Вы могли бы думать об этом как о проблеме графа, где набор (1,2,3) связан с множеством (5,2,6) через 2. А затем использовать стандартный алгоритм, чтобы уточнить подключенный подчиненный графики.

Вот быстрая реализация на python:

nodes = [ [1,2,3], [2,4,5], [6,7,8], [10,11,12], [7,10,13], [12], [] ]
links = [ set() for x in nodes ]

#first find the links
for n in range(len(nodes)):
    for item in nodes[n]:
        for m in range(n+1, len(nodes)):
            if (item in nodes[m]):
                links[n].add(m)
                links[m].add(n)

sets = []
nodes_not_in_a_set = range(len(nodes))

while len(nodes_not_in_a_set) > 0:
    nodes_to_explore = [nodes_not_in_a_set.pop()]
    current_set = set()
    while len(nodes_to_explore) > 0:
        current_node = nodes_to_explore.pop()
        current_set.add(current_node)
        if current_node in nodes_not_in_a_set:
            nodes_not_in_a_set.remove(current_node)
        for l in links[current_node]:
            if l not in current_set and l not in nodes_to_explore:
                nodes_to_explore.append(l)
    if len(current_set) > 0:
        sets.append(current_set)

for s in sets:
    print [nodes[n] for n in s]

выход:

[[]]
[[6, 7, 8], [10, 11, 12], [7, 10, 13], [12]]
[[1, 2, 3], [2, 4, 5]]

Answer 3

Подумав об этом еще немного, я придумал это:

1. Создать таблицу с именем groups со столбцами (group_id, set_id)
2. Сортировка таблицы sets по element. Теперь должно быть легко найти дубликаты элементов.
3. Выполните итерацию по таблице множеств, и когда вы найдете дублирующий элемент, выполните:
   1. если одно из полей set_id существует в таблице groups, добавьте другое с таким же group_id.
   2. Если ни set_id не существует в таблице groups, создайте новый идентификатор группы и добавьте оба set_id s в таблицу groups.

В конце концов у меня должна быть таблица groups, содержащая все наборы.

Это не чистый SQL, но кажется, что O (nlogn), поэтому я думаю, что смогу с этим смириться.

Ответ Мэтта кажется более правильным, но я не уверен, как реализовать это в моем случае.

Answer 4

Это, вероятно, довольно неэффективно, но, по крайней мере, должно работать: начните с ключа, выберите все группы, содержащие этот ключ, выберите все ключи этих групп, выберите все группы, содержащие эти ключи и т. Д., И как только шаг не добавляет новых ключей или групп, у вас есть список всех групп одного подграфа. Исключите их и повторяйте с самого начала, пока у вас не останется данных.

С точки зрения SQL, мне понадобится хранимая процедура, я думаю. С RECURSIVE может вам как-то помочь, но у меня пока нет с этим опыта, и я не уверен, что он доступен в вашей базе данных БД.