Свернуть список списков, чтобы устранить избыточность

Question

У меня есть несколько длинных списков списков связанных объектов, которые я хотел бы группировать, чтобы уменьшить избыточность. Псевдокод:

>>>list_of_lists = [[1,2,3],[3,4],[5,6,7],[1,8,9,10]...] 
>>>remove_redundancy(list_of_lists) 
[[1,2,3,4,8,9,10],[5,6,7]...] 

Таким образом, списки, содержащие одни и те же элементы, будут сворачиваться в отдельные списки. Свертывание их легко, как только я найду списки для объединения, я могу сделать списки в наборах и принять их союз, но я не уверен, как сравнивать списки. Нужно ли делать серию циклов for?

Моя первая мысль состояла в том, что я должен прокручивать и проверять, находится ли каждый элемент в подсписке в любом из других списков, если да, объединить списки и затем начать все сначала, но это кажется ужасно неэффективным. Я сделал поиск и нашел это: Python - dividing a list-of-lists to groups, но мои данные не структурированы. Кроме того, мои фактические данные представляют собой ряд строк и, следовательно, не сортируются в каком-либо значимом смысле.

Я могу написать некоторый gnarly цикл, чтобы сделать эту работу, но мне было интересно, есть ли какие-либо встроенные функции, которые упростили бы это сравнение. Может быть, что-то в list comprehensions?

Answer 1

Я думаю, что это разумно эффективный способ сделать это, если я правильно понимаю ваш вопрос. В результате здесь будет список наборов.

Может быть недостающим немного знаний был d & g (также написано d.intersection(g)) для нахождения множества пересечение, наряду с тем, что пустое множество является «falsey» в Python

data = [[1,2,3],[3,4],[5,6,7],[1,8,9,10]] 

result = [] 

for d in data: 
    d = set(d) 

    matched = [d] 
    unmatched = [] 
    # first divide into matching and non-matching groups 
    for g in result: 
     if d & g: 
      matched.append(g) 
     else: 
      unmatched.append(g) 
    # then combine all matching groups into one group 
    # while leaving unmatched groups intact 
    result = unmatched + [set().union(*matched)] 

print(result) 
# [set([5, 6, 7]), set([1, 2, 3, 4, 8, 9, 10])] 

Мы начинаем с каких-либо групп в все (result = []). Затем мы берем первый список из данных. Затем мы проверяем, какая из групп пересекает этот список, а какие нет. Затем мы объединяем все эти сопоставимые группы вместе со списком (достигнутый путем, начиная с matched = [d]). Мы не трогаем несогласованные группы (хотя, возможно, некоторые из них будут объединены в более позднюю итерацию). Если вы добавите строку print(result) в каждый цикл, вы сможете увидеть, как она создана.

Объединение всех наборов в matched вычисляется set().union(*matched). Для справки:

• Pythonic Way to Create Union of All Values Contained in Multiple Lists
• What does the Star operator mean?

Answer 2

Я предполагаю, что вы хотите объединить списки, которые содержат какой-либо общий элемент.

Вот функция, которая выглядит эффективно (насколько мне известно), если любые два списка содержат, по меньшей мере, один общий элемент (в соответствии с оператором ==)

import functools #python 2.5+ 
def seematch(X,Y): 
    return functools.reduce(lambda x,y : x|y,functools.reduce(lambda x,y : x+y, [[k==l for k in X ] for l in Y])) 

было бы еще быстрее, если вы будет использовать сверток, который может быть прерван при нахождении «истинно», как описано здесь: Stopping a Reduce() operation mid way. Functional way of doing partial running sum

Я пытался найти элегантный способ итерации быстро после того, что на месте, но я думаю, что это хороший способ будет просто перекручивание один раз и создание другого контейнера, который будет содержать «mer ged ". Вы повторяете один раз в списках, содержащихся в исходном списке, и для каждого нового списка, созданного в списке прокси.

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

Я знаю, что это неполный ответ - надеюсь, что это помогло!