Как эффективно группировать пары на основе общего элемента?

Question

У меня есть список пар (кортежей), для упрощения что-то вроде этого:

L = [("A","B"), ("B","C"), ("C","D"), ("E","F"), ("G","H"), ("H","I"), ("G","I"), ("G","J")]

Используя python, я хочу эффективно разделить этот список на:

L1 = [("A","B"), ("B","C"), ("C","D")]
L2 = [("E","F")]
L3 = [("G","H"), ("G","I"), ("G","J"), ("H","I")]

Как эффективно разбить список на группы пар, где для пар в группе всегда должна быть хотя бы одна пара, которая разделяет один элемент с другими? Как указано в одном из ответов, это на самом деле проблема сети .Цель состоит в том, чтобы эффективно разделить сеть на отдельные (изолированные) части сети.

Типовые списки, кортежи (наборы) могут быть изменены для достижения более высокой эффективности.

Answer 1

Это больше похоже на проблему с сетью, поэтому мы используем networks

import networkx as nx
G=nx.from_edgelist(L)

l=list(nx.connected_components(G))
# after that we create the map dict , for get the unique id for each nodes
mapdict={z:x for x, y in enumerate(l) for z in y }
# then append the id back to original data for groupby 
newlist=[ x+(mapdict[x[0]],)for  x in L]
import itertools
#using groupby make the same id into one sublist
newlist=sorted(newlist,key=lambda x : x[2])
yourlist=[list(y) for x , y in itertools.groupby(newlist,key=lambda x : x[2])]
yourlist
[[('A', 'B', 0), ('B', 'C', 0), ('C', 'D', 0)], [('E', 'F', 1)], [('G', 'H', 2), ('H', 'I', 2), ('G', 'I', 2), ('G', 'J', 2)]]

---

, чтобы соответствовать вашему выводу

L1,L2,L3=[[y[:2]for y in x] for x in yourlist]
L1
[('A', 'B'), ('B', 'C'), ('C', 'D')]
L2
[('E', 'F')]
L3
[('G', 'H'), ('H', 'I'), ('G', 'I'), ('G', 'J')]

Answer 2

Эффективный и Pythonic подход заключается в преобразовании списка кортежей в набор frozensets в качестве пула кандидатов, а в цикле while создайте набор в качестве группы и используйте вложенный цикл while для продолжения расширениягруппа, добавив первый набор кандидатов, а затем выполнив объединение набора с другими наборами кандидатов, которые пересекаются с группой, пока не останется больше пересекающихся кандидатов, после чего вернитесь во внешний цикл, чтобы сформировать новую группу:

pool = set(map(frozenset, L))
groups = []
while pool:
    group = set()
    groups.append([])
    while True:
        for candidate in pool:
            if not group or group & candidate:
                group |= candidate
                groups[-1].append(tuple(candidate))
                pool.remove(candidate)
                break
        else:
            break

Учитывая ваш пример ввода, groups станет:

[[('A', 'B'), ('C', 'B'), ('C', 'D')],
 [('G', 'H'), ('H', 'I'), ('G', 'J'), ('G', 'I')],
 [('E', 'F')]]

Имейте в виду, что наборы неупорядочены в Python, поэтому порядок вывода выше не соответствует вашему ожидаемому выводу, но для вашей цели порядок не должен иметь значения.

Answer 3

Вы можете использовать следующий код:

l = [("A","B"), ("B","C"), ("C","D"), ("E","F"), ("G","H"), ("H","I"), ("G","I"), ("G","J")]

result = []
if len(l) > 1:
  tmp = [l[0]]
  for i in range(1,len(l)):
    if l[i][0] == l[i-1][1] or l[i][1] == l[i-1][0] or l[i][1] == l[i-1][1] or l[i][0] == l[i-1][0]:
      tmp.append(l[i])
    else:
      result.append(tmp)
      tmp = [l[i]]
  result.append(tmp)
else:
  result = l

for elem in result:
  print(elem)

выход

[('A', 'B'), ('B', 'C'), ('C', 'D')]
[('E', 'F')]
[('G', 'H'), ('H', 'I'), ('G', 'I'), ('G', 'J')]

Примечание: этот код основан на гипотезе, что ваш исходный массив отсортирован. Если это не так, это не сработает, поскольку для создания групп достаточно одного прохода по всему списку (сложность O(n)).

Пояснения:

• result будет хранить ваши группы
• if len(l) > 1: если у вас есть только один элемент в вашем списке или пустой список, нет необходимости выполнять какую-либо обработку, у вас есть ответ
• Вы пройдете один проход по каждому элементу списка и сравните 4 возможных равенства между кортежем в позиции i и равенством в позиции i-1.
• tmp используется для построения ваших групп, при условии, что выполняется условие, вы добавляете кортежи в tmp
• когда условие не соблюдается, вы добавляете tmp (текущую группу, созданную к результату, повторно включите tmp с текущим кортежем) и продолжаете.

Answer 4

• Инициализировать список групп как пустой
• Пусть (a, b) будет следующей парой
• Соберите все группы, которые содержат элементы с a или b
• Удалите их всех, присоединитесь к ним, добавьте (a, b) и вставьте в качестве новой группы
• Повторяйте до готовности

Это было бы что-то вроде этого:

import itertools, functools

def partition(pred, iterable):
    t1, t2 = itertools.tee(iterable)
    return itertools.filterfalse(pred, t1), filter(pred, t2)

groups = []
for a, b in L:
    unrelated, related = partition(lambda group: any(aa == a or bb == b or aa == b or bb == a for aa, bb in group), groups)
    groups = [*unrelated, sum(related, [(a, b)])]

Answer 5

Вы можете использовать цикл while и начать итерацию с первого члена L (используя цикл for внутри).Проверьте весь список, если какой-либо участник (любой из двух) является общим или нет.Затем добавьте его в список L1 и вытяните этот элемент из исходного списка L. Затем цикл while будет выполняться снова (пока список L не будет пустым).И цикл for внутри будет работать для каждого элемента в списке, чтобы добавить в новый список L2.Вы можете попробовать это.(Я приведу код, который не помогает)