不仅涉及多个集合的交集，还包括并集和更新。

Question

我将尝试在Python中查找两个“集合”之间的交集。但是，一旦找到，我需要“联合”这两个集合并再次迭代“字典”，直到没有进一步的更改。

类似于这样：

dict_={'a': {1,3,4}, 'b': {0,5,4}, 'c': {0,6,5},'e':{7,9}}

What i need:

result={'abc':{1,3,4,0,5,4,0,6,5}, 'e':{7,9}}

以下是我目前所做的：

dict_={'a': {1,3,4}, 'b': {0,5,4}, 'c': {0,6,5},'e':{7,9}}    
flag=True
while flag:
    done=False
    for key in list(dict_):
        if done:        ## to break outer loop
            del dict_[remove1]
            del dict_[remove2]
            break
        for newKey in list(dict_):
            if key==newKey:
                continue
            if len(set.intersection(dict_[key],dict_[newKey]))>0:
                added_key=str(key)+str(newKey)
                dict_[added_key]=set.union(dict_[key],dict_[newKey])
                remove1=key
                remove2=newKey
                done=True
                break    ## to break inner loop
    flag=False     ## Here is the problem. I do not know what to do

这段代码的结果：

dict_
#{'ab': {0, 1, 3, 4, 5}, 'c': {0, 5, 6}, 'e': {7, 9}}

- practitioner

---

您期望的答案 result={'abc':{1,3,4,0,5,4,0,6,5}, 'e':{7,9}} 不可能实现，因为 {1,3,4,0,5,4,0,6,5} 不是一个有效的集合。 - SillyBear

聚合后的键名顺序可能与原始键名的顺序不同。 - CristiFati

我猜这是有效的。一旦我将'a'和'b'合并，因为它们相交于4，那么'c'将与新集合'ab'相交，因为有5。 - practitioner

这是无效的，因为集合不能有重复元素。 - Vivek Pabani

抱歉，你是对的。我的意思是这个 {0, 1, 3, 4, 5, 6}。我的想法是，一旦我将 'a' 和 'b' 合并，因为它们在 4 处相交，那么 'c' 将与新集合 'ab' 相交，因为有 5。 - practitioner

这是关于编程的内容，请将其从英语翻译成中文。请仅返回翻译后的文本，不要进行解释。谢谢。 - practitioner

Answer 1

正如评论中有人指出的那样，您所期望的结果集是无效的。假设您想要联接键并合并值集，直到它们有任何公共点，您可以这样做：

d ={'a': {1,3,4}, 'b': {0,5,4}, 'c': {0,6,5},'e':{7,9}}

flag = True

while (flag):
    keys = list(d.keys())
    outer_break = False
    for i in range(len(keys)-1):
        inner_break = False
        for j in range(i+1, len(keys)):
            if len(set.intersection(d[keys[i]], d[keys[j]])) > 0:
                d[keys[i] + keys[j]] = set.union(d[keys[i]], d[keys[j]])
                del d[keys[i]]
                del d[keys[j]]
                inner_break = True
                break
        if inner_break:
            outer_break = True
            break
    if not outer_break:
        flag = False

print (d)
# {'e': {9, 7}, 'cab': {0, 1, 3, 4, 5, 6}} 

您也可以使用递归函数来实现这个功能，代码如下：

dd ={'a': {1,3,4}, 'b': {0,5,4}, 'c': {0,6,5},'e':{7,9}}

def reduce_dict(d):
    keys = list(d.keys())
    for i in range(len(keys)-1):
        for j in range(i+1, len(keys)):
            if len(set.intersection(d[keys[i]], d[keys[j]])) > 0:
                d[keys[i] + keys[j]] = set.union(d[keys[i]], d[keys[j]])
                del d[keys[i]]
                del d[keys[j]]
                return reduce_dict(d)
    return d

dd = reduce_dict(dd)

print(dd)
# {'e': {9, 7}, 'cab': {0, 1, 3, 4, 5, 6}} 

- Vivek Pabani

Answer 2

我建议使用itertools.combinations来查看所有可能的唯一键组合，您可以避免使用太多标志，而是使用一个seen set()，如下所示：

from itertools import combinations

dict_={'a': {1,3,4}, 'b': {0,5,4}, 'c': {0,6,5},'e':{7,9}}

for i in range(2,len(dict_)+1): # For length of dict from 2
    # Initialize the "seen" list
    seen_keys = set()
    for combination in list(combinations(dict_, 2)): # Get possible key combinations of 2
            keys_in_combination = [dict_[x] for x in combination] # And their values in a list

            if len(set.intersection(*keys_in_combination)): # * Expands the list into the arguments
                # Make key names alphabetical with no duplicate letters.
                added_key = "".join(sorted(set(x for y in combination for x in str(y))))
                # Join 2 sets under new key
                dict_[added_key] = set.union(*keys_in_combination)
                for seen_key in combination:
                    # create a seen list (for the deletion below)
                    seen_keys.add(seen_key)

    # Delete the keys which have been joined to others
    for key in dict_.copy():
        if len(key) < i and key in seen_keys:
            del dict_[key]

print(dict_)

结果：

{'abc': set([0, 1, 3, 4, 5, 6]), 'e': set([9, 7])}

这种方法也适用于字典，其中的组合可能比“abc”更长。

- Zhenhir

Answer 3

一个非常优化的方法是使用一个字典项列表，然后循环遍历该列表，如果它们有任何交集，则递归更新这些项。

def find_intersection(m_list):
    for i, (key_1, v) in enumerate(m_list) : 
        for j, (key_2, k) in enumerate(m_list[i+1:],i+1):
        if v & k:
            m_list[i] = key_1 + key_2, v.union(m_list.pop(j)[1])
            return find_intersection(m_list)
    return m_list

演示：

In [10]: find_intersection(list(mydict.items()))
Out[10]: [('abc', {0, 1, 3, 4, 5, 6}), ('e', {7, 9})]

- Mazdak