python - 递归以找到 Python 中集合之间的共性

Question

我有多个集合(数量未知)，我想找到集合之间的共性，如果集合之间有匹配(80% 匹配)，我想合并这 2 个集合，然后重新运行新的集合我从一开始就对所有其他组进行了设置。

例如:

A : {1,2,3,4}
B : {5,6,7}
C : {1,2,3,4,5}
D : {2,3,4,5,6,7}

然后 A 运行，A 和 B 之间没有共性，然后它针对 C 运行 A，达到了共性目标，因此我们现在有了一个新的集合 AC = {1,2,3,4,5}，现在我们将 AC 与 B 进行比较，它没有达到阈值，但 D 达到了阈值，因此我们有一个新的 ACD 集，现在我们再次运行，现在我们与 B 命中。

我目前正在使用 2 个循环，但只有当我比较 2 个循环时才能解决这个问题。

为了计算共性，我使用以下计算:

overlap = a_set & b_set
universe = a_set | b_set
per_overlap = (len(overlap)/len(universe))

我认为解决方案应该是一个递归函数，但我不太确定如何编写它，我对 Python 有点陌生，或者也许有一种不同且简单的方法来做到这一点。

Answer 1

我相信这正是您所寻找的。复杂性非常可怕，因为每次获得匹配时都会重新开始。不需要递归。

def commonality(s1, s2):
    overlap = s1 & s2
    universe = s1 | s2
    return (len(overlap)/len(universe))

def set_merge(s, threshold=0.8):
    used_keys = set()
    out = s.copy()
    incomplete = True
    while incomplete:
        incomplete = False
        restart = False
        for k1, s1 in list(out.items()):
            if restart:
                incomplete = True
                break
            if k1 in used_keys:
                continue
            for k2, s2 in s.items():
                if k1==k2 or k2 in used_keys:
                    continue
                print(k1, k2)
                if commonality(s1, s2) >= threshold:
                    out.setdefault(k1+k2, s1 | s2)
                    out.pop(k1)
                    if k2 in out:
                        out.pop(k2)
                    used_keys.add(k1)
                    used_keys.add(k2)
                    restart = True
                    break
    out.update({k:v for k,v in s.items() if k not in used_keys})
    return out

对于您的特定示例，它仅合并 A 和 C，因为任何其他组合都低于阈值。

set_dict = {
    'A' : {1,2,3,4},
    'B' : {5,6,7},
    'C' : {1,2,3,4,5},
    'D' : {2,3,4,5,6,7},
}
set_merge(set_dict)
# returns:
{'B': {5, 6, 7},
 'D': {2, 3, 4, 5, 6, 7},
 'AC': {1, 2, 3, 4, 5}}