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

Question

У меня есть словарь, который похож на следующее:

dict1 = {'key1':['1','2','3'],'key2':['3','4','5'],'key3':['6','7','8']}

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

dict1 = {'key1':['1','2','3','4','5'],'key3':['6','7','8']}

Обратите внимание, как key2 был устранен. Будь то ключ1 или ключ2, который исключен, не имеет значения. Я только смог идентифицировать повторы, но не сумел объединить их итеративным способом. Спасибо

Answer 1

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

vals = {k: set(val) for k, val in dict1.items()}

for key, val in dict1.copy().items():
    for k, v in vals.copy().items():
        if k == key:
            continue
        if v.intersection(val):
            union = list(v.union(val))
            dict1[key] = union
            del vals[k]
            del dict1[k]

Если вы хотите объединить все:

vals = {k: set(val) for k, val in dict1.items()}
unioned = set()
srt = sorted(dict1.keys())
srt2 = srt[:]
for key in srt:
    for k in srt2:
        if k == key:
            continue
        if vals[k].intersection(dict1[key]) and key not in unioned:
            unioned.add(k)
            dict1[key] = list(vals[k].union(dict1[key]))
            srt2.remove(k)

for k in unioned:
    del dict1[k]

Answer 2

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

dict_out = {}
processed = set()
for k1, v1 in dict_in.items():
    if k1 not in processed:
        processed.add(k1)
        vo = v1
        for k2, v2 in dict_in.items():
            if k2 not in processed and set(v1) & set(v2):
                vo = sorted(list(set(vo + v2)))
                processed.add(k2)
        dict_out[k1] = vo

Это для:

dict_in = {'key1': ['1', '2', '3'], 'key2': ['3', '4', '5'], 'key3': ['6', '7', '8']}

дает:

{'key1': {'1', '2', '3', '4', '5'}, 'key3': ['6', '7', '8']}

И для:

dict_in = {'key1': ['1', '2', '3'], 'key2': ['3', '4', '5'],
           'key3': ['6', '7', '8'], 'key4': ['7', '9']}

дает:

{'key1': {'1', '2', '3', '4', '5'}, 'key3': {'6', '7', '8', '9'}}

И, наконец, для:

dict_in = {'key1': ['1', '2', '3'], 'key2': ['3', '4', '5'],
           'key3': ['6', '7', '8'], 'key4': ['5', '6', '7']}

это дает:

{'key1': {'1', '2', '3', '4', '5'}, 'key3': {'5', '6', '7', '8'}}

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

ОП потребовал, чтобы даже результаты слияний были объединены друг с другом. Чтобы достичь этого, мы можем обернуть приведенный выше код в цикл следующим образом:

d = dict_in
processed = set([None])
while processed:
    dict_out = {}
    processed = set()
    for k1, v1 in d.items():
        if k1 not in processed:
            vo = v1
            for k2, v2 in d.items():
                if k1 is not k2 and set(vo) & set(v2):
                    vo = sorted(list(set(vo + v2)))
                    processed.add(k2)
            dict_out[k1] = vo
    d = dict_out

Тогда для:

dict_in = {'key1': ['1', '2', '3'], 'key2': ['3', '4', '5'],
           'key3': ['6', '7', '8'], 'key4': ['5', '6', '7']}

мы получаем:

{'key4': ['1', '2', '3', '4', '5', '6', '7', '8']}

и для:

dict_in = {'key1': ['1', '2', '3'], 'key2': ['3', '4', '5'],
           'key3': ['4', '6', '7'], 'key4': ['8', '9']}

мы получаем:

{'key1': ['1', '2', '3', '4', '5', '6', '7'], 'key4': ['8', '9']}

Answer 3

У меня есть более компактный метод.

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

dict1 = {'key1':['1','2','3'],'key2':['3','4','5'],'key3':['6','7','8']}

# Index your key of dict
l = list(enumerate(sorted(dict1.keys())))

# nested loop
for i in xrange(len(dict1)):
    for j in xrange(i+1,len(dict1)):
        i_key, j_key = l[i][1], l[j][1]
        i_value, j_value = set(dict1[i_key]), set(dict1[j_key])
        # auto detect: if the values have common element to do union
        if i_value & j_value:
            union_list = sorted(list(i_value | j_value))
            dict1[i_key] = union_list
            del dict1[j_key]

print dict1
#{'key3': ['6', '7', '8'], 'key1': ['1', '2', '3', '4', '5']}