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

Вы могли думать о нем как о проблеме графика, где набор (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 этому была бы нужна хранимая процедура, я думаю. С РЕКУРСИВНЫМ мог бы помочь Вам так или иначе, но у меня еще нет опыта с ним, и я не уверен, что это доступно на Вашем бэкенде DB.

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

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

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

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

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