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

StackOverflow https://stackoverflow.com/questions/178913

  •  05-07-2019
  •  | 
  •  

Вопрос

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

[ (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, но я был бы доволен общим направлением решения.

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

Это было полезно?

Решение

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

  • для всех i = от 1 до N выполните:
  • если i был помечен каким-то j < i, затем продолжайте (я имею в виду переход к следующему i).
  • else flood_from(i,я)

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

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

Затем теги наборов выдают вам подключенные компоненты, которые вы ищете.

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

  • S = выбрать все строки, где set_id == i
  • установите для ТЕГА значение i для строк в S
  • S' = выбрать все строки, где ТЕГ не задан и где элемент находится в элементах
  • пока S' не пусто, выполните
  • ---- установите для ТЕГА значение i для строк в S'
  • ---- S" = выбрать все строки, где ТЕГ не задан и где элемент находится в элементе (Ах')
  • ---- S = S объединение S'
  • ---- S' = S"
  • возвращает set_id(Ы)

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

  • если A = {A1, ..., An} - это набор множеств, определяющий union(A) = A1 профсоюз ...объединение Аn
  • если K = {k1, ..., кp} представляет собой набор целых чисел, определяющих инцидентности(K) = множество множеств, которые пересекают K

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

  1. K = S
  2. K' = инциденты (объединение(K)).
  3. если K == K', то верните K, иначе K = K' и перейдите к 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]]

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

С точки зрения SQL, я думаю, для этого потребовалась бы хранимая процедура.ИСПОЛЬЗОВАНИЕ RECURSIVE может вам как-то помочь, но у меня пока нет никакого опыта работы с этим, и я не уверен, что это доступно в вашем бэкэнде базы данных.

Поразмыслив об этом еще немного, я пришел к следующему выводу:

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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top