Найти дублирующий элемент в списке списков

Question

Я ищу идеи Python для решения следующей проблемы.

Учитывая список списков ...

[[20, 21, 22], [17, 18, 19, 20], [10, 11, 12, 13]] 

Если есть дубликат элемент, который является общим между любым или всеми списками, вернуть True. Если все элементы уникальны, верните False.

В приведенном выше примере 20 является общим и вернет True. Пример ниже вернет False, потому что все числа уникальны между списками.

[[20, 21, 22], [17, 18, 19], [10, 11, 12, 13]] 

И, наконец, тестирование дубликатов в отдельном списке не требуется, поскольку числа всегда являются последовательными.

FYI - эта проблема будет использоваться для оптимизации ежемесячного графика членов экипажа авиакомпании. Каждый список представляет собой поездки на 3, 4 или 5 дней, которые не могут пересекаться.

BTW - эта проблема не является заданием, а личным стремлением работать меньше и получать больше :) Жаль, что было неясно. Я попробовал метод грубой силы, который работает, но надеялся на более элегантный метод Pythonic. Я ценю все ответы, поскольку они приводят меня в новые области программирования на Python.

Answer 1

Предполагая, что вы ищете конкретной цели (ваш вопрос был неясным):

def find_dupe(lists, target): 
    seen = set() 
    for lst in lists: 
     for item in lst: 
      if item == target and item in seen: 
       return True 
      seen.add(item) 

DEMO:

>>> find_dupe([[20, 21, 22], [17, 18, 19, 20], [10, 11, 12, 13]], 
       20) 
True 

Если это не так, то вы можете просто вырезать item == target состояние

def find_dupe(lists): 
    seen = set() 
    for lst in lists: 
     for item in lst: 
      if item in seen: 
       yield item 
      seen.add(item) 

Answer 2

num = Counter(i for j in alist for i in j) # flatten list into a single dimension 
dup = [k for k, v in num.items() if v > 1] # checks the dict for duplicate values 

Answer 3

Если вы готовы отказаться от элегантности списка понимания, вы можете сделать следующее:

seen, dups = set(), set() 
for l in ll: 
    dups = dups.union(seen.intersection(set(l))) 
    seen = seen.union(set(l)) 

Ваш ответ должен быть в dups.

Редактировать

Как Steven Rumbalski указал ниже, set внутри доводов set -Член операций, является избыточным (и неоправданно дорого).

Answer 4

>>> from collections import Counter 
>>> list_of_list = [[20, 21, 22], [17, 18, 19, 20], [10, 11, 12, 13]] 
>>> counts = Counter(item for sublist in list_of_list for item in sublist) 
>>> repeated_items = [item for item, count in counts.items() if count > 1] 
>>> repeated_items 
[20] 

Answer 5

Что-то вроде этого:

l = [[20, 21, 22], [17, 18, 19, 20], [10, 11, 12, 13]] 
dupes = [] 
flat = [item for sublist in l for item in sublist] 
for f in flat: 
    if flat.count(f) > 1: 
     if f not in dupes: 
      dupes.append(f) 

if dupes: 
    return True 
else: 
    return False 

Answer 6

Я предлагаю вам попробовать это:

def find_dup(listOfLists): 
    for index in range(len(listOfLists) - 1) 
     result = [filter(lambda x: x in listOfLists[index], otherLists) for otherLists in listOfLists[index+1:]] 
     if result: 
      return True 
    return False 

Идея заключается в том, чтобы посмотреть на первый список (listOfLists [0]) и проверьте, любой из его элементов повторяется среди других списков (listOfLists [1:]), в положительном случае верните True, в отрицательном, посмотрите на второй список (listOfLists [1]) и снова взгляните на другие списки (listOfLists [2:]) и s o on. Важно избегать проверки каждый раз с самого начала.

Я не смог проверить этот пример, но я думаю, что он должен работать :).

Надеюсь, что эта помощь.

Answer 7

Aiming для эффективности здесь.

def duplicates_exist(ll): 
    seen = set() 
    see = seen.add 
    for l in ll: 
     for element in set(l): 
      if element in seen: 
       return True 
      see(element) 
    return False 

@Stefan Pochmann's answer заставил меня понять, что у меня был ненужный генератор ранее. > _ <

Answer 8

>>> seen = set() 
>>> any(element in seen or seen.add(element) 
     for lst in lists for element in set(lst)) 
True 

Я использую только set(lst) вместо того, чтобы просто lst, потому что не ясно, может ли Подсписок содержать дубликаты.

Как на это указывает @Shashank, это эффективно, поскольку оно останавливается при первом найденном дубликате (точно так же, как Shashank's solution). Если есть много подписок, но в первых двух экземплярах есть дубликат, то оставшиеся даже не будут рассмотрены. Таким образом, это быстрее, чем решения, которые сначала собирают все дубликаты извне, а затем превращают их в логические только после этого.

Обновление: @ комментарий abarnert заставил меня думать об этом:

>>> max(Counter(chain.from_iterable(ll)).values()) > 1 
True 

или короче (но медленнее):

>>> max(Counter(sum(lists, [])).values()) > 1 
True 

Эти два не обрабатывать дубликаты внутри одного подсписка, но я считаю разумным предположить, что этого не может быть, поскольку в противном случае спецификация должна действительно так говорить или, по крайней мере, пример должен иметь один.