Найти перекрывающиеся элементы в списке кортежей?

Question

Исходя из моего понимания функции пересечения, он находит полное перекрытие между элементами в списке. Например:

tup_1 = [(1,2,3),(4,5,6)]
tup_2 = [(4,5,6)]
ol_tup = set(tup_1).intersection(tup_2)
print ol_tup

даст:

set([(4, 5, 6)])

Однако предположим, что мой список кортежей настроен так:

tup_1 = [(1,2,3),(4,5,5)]
tup_2 = [(4,5,6)]

Где есть перекрытие в 2 элементах 2-го кортежа в tup_1 и 1-го кортежа в tup_2. Если я хочу, чтобы Python вернул эти 2 кортежа: (4,5,5) и (4,5,6), есть ли более простой способ, чем этот вложенный цикл (ниже)?

for single_tuple_1 in tup_1:
    for single_tuple_2 in tup_2:
        if single_tuple_1[0] == single_tuple_2[0] and single_tuple_1[1] == single_tuple_2[1]:
            print single_tuple_1,single_tuple_2

РЕДАКТИРОВАТЬ:

Для этого случая предположим, что порядок имеет значение, и предположим, что кортежи содержат 5 элементов:

tup_1 = [(1,2,3,4,5),(4,5,6,7,8),(11,12,13,14,15)]
tup_2 = [(1,2,3,4,8),(4,5,1,7,8),(11,12,13,14,-5)]

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

[(1,2,3,4,5),(1,2,3,4,8),(11,12,13,14,15),(11,12,13,14,-5)]

Как изменился бы код, чтобы приспособиться к этому?

Answer 1

Если вы хотите вернуть все пары «перекрывающихся» кортежей, то нет никакого способа сравнить все пары, то есть квадратичный алгоритм. Но вы могли бы сделать код немного более элегантным, используя понимание списка, product для комбинаций и zip и sum для сравнения:

>>> tup_1 = [(1,2,3),(4,5,5),(7,8,9)]

>>> tup_2 = [(4,5,6),(0,5,5),(9,8,7)]

>>> [(a, b) for (a, b) in itertools.product(tup_1, tup_2)
...         if sum(1 for ai, bi in zip(a, b) if ai == bi) >= 2]
[((4, 5, 5), (4, 5, 6)), ((4, 5, 5), (0, 5, 5))]

Примечание. При этом проверяется, имеют ли два кортежа один и тот же элемент хотя бы в двух позициях, т. Е. Порядок имеет значение. Если порядок не имеет значения, вы можете вместо этого преобразовать a и b в set и проверить размер их пересечения, но это может не сработать для повторяющихся чисел, то есть пересечение (1,1,2) и (1,1,3) будет просто быть 1 вместо 2.

Если вы хотите сопоставить только первые два или первые два и два последних элемента, вы можете сравнить фрагменты кортежей в соответствии с дизъюнкцией:

>>> [(a, b) for (a, b) in itertools.product(tup_1, tup_2)
...         if a[:2] == b[:2]]
[((4, 5, 5), (4, 5, 6))]

>>> [(a, b) for (a, b) in itertools.product(tup_1, tup_2)
...         if a[:2] == b[:2] or a[-2:] == b[-2:]]
[((4, 5, 5), (4, 5, 6)), ((4, 5, 5), (0, 5, 5))]

Answer 2

Это один из способов использования списочного понимания.Как написано, логика проверяет перекрытие по крайней мере 2 элементов.

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

from itertools import chain

tup_1 = [(1,2,3),(4,5,5)]
tup_2 = [(4,5,6)]

y = sorted(tup_2[0])
res = [i for i in chain(tup_1, tup_2) if
       sum(i==j for i, j in zip(sorted(i), y)) > 1]

print res

[(4, 5, 5), (4, 5, 6)]