Как проверить, если ключ/значение повторяется в другом месте в словаре, используя Python

Question

У меня есть словарь в Python, как:

dict = {'dog':['milo','otis','laurel','hardy'], 
     'cat':['bob','joe'], 
     'milo':['otis','laurel','hardy','dog'], 
     'hardy':['dog'],'bob':['joe','cat']} 

... и я хочу, чтобы определить, если ключ существует в другом месте в словаре (в другом списке значений). Есть еще вопросы, которые я могу найти, чтобы узнать, существует ли элемент в словаре, но это не мой вопрос. То же самое касается элементов в каждом списке значений, чтобы идентифицировать элементы, которые не существуют в ДРУГИХ ключах и их ассоциированные значения в словаре.

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

unique.dict = {'cluster1':['dog','milo','otis','laurel','hardy'], 
       'cluster2':['cat','bob','joe'] } 

Это прослеживание вопроса In Python, count unique key/value pairs in a dictionary

Answer 1

Похоже, что связь симметрична, но ваши данные отсутствуют (например, нет ключа 'otis'). первая часть предполагает, что она симметрична, поэтому не имеет значения, с чего мы начинаем.

(Если ваши данные на самом деле является симметричным, то пропустите эту часть.)

Python 2,7

from collections import defaultdict 

data = {'dog':['milo','otis','laurel','hardy'],'cat':['bob','joe'],'milo':['otis','laurel','hardy','dog'],'hardy':['dog'],'bob':['joe','cat']} 

# create symmetric version of data 
d = defaultdict(list) 
for key, values in data.iteritems(): 
    for value in values: 
     d[key].append(value) 
     d[value].append(key) 

visited = set() 
def connected(key): 
    result = [] 
    def connected(key): 
     if key not in visited: 
      visited.add(key) 
      result.append(key) 
      map(connected, d[key]) 
    connected(key) 
    return result 

print [connected(key) for key in d if key not in visited] 

Python 3.3

from collections import defaultdict 

data = {'dog':['milo','otis','laurel','hardy'],'cat':['bob','joe'],'milo':['otis','laurel','hardy','dog'],'hardy':['dog'],'bob':['joe','cat']} 

# create symmetric version of data 
d = defaultdict(list) 
for key, values in data.items(): 
    for value in values: 
     d[key].append(value) 
     d[value].append(key) 

visited = set() 
def connected(key): 
    visited.add(key) 
    yield key 
    for value in d[key]: 
     if key not in visited: 
      yield from connected(value) 

print([list(connected(key)) for key in d if key not in visited]) 

Результат

[['otis', 'milo', 'laurel', 'dog', 'hardy'], ['cat', 'bob', 'joe']] 

Performance

O(n), где n является общее количество ключей и значений в data (в вашем случае 17, если я правильно отсчитывать).

Answer 2

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

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

def does_key_exist_in_other_value(d, key): 
    for k, v in d.items(): 
     if k != key and key in v: 
      return True 

Вы могли бы, конечно, конденсируется, что в однострочника с genexpr и any:

return any(key in v for k, v in d.items() if k != key) 

Но более разумной задачей было бы использовать лучшую структуру данных. По крайней мере, используйте вместо списков как набор значений (что не упростит ваш код, но сделает его намного быстрее - если у вас есть ключи К и V общих элементов по вашим значениям, он будет работать в O (K) вместо O (KV)

Но на самом деле, если вы хотите посмотреть вещи, построить Dict посмотреть вещи в:.

inv_d = defaultdict(set) 
for key, value in d.items(): 
    for v in value: 
     inv_d[v].add(key) 

И теперь, ваш код просто:

def does_key_exist_in_other_value(inv_d, key): 
    return inv_d[key] != {key}