Python设置交集问题

Question

我有三套:

s0 = [set([16,9,2,10]), set([16,14,22,15]), set([14,7])]   # true, 16 and 14
s1 = [set([16,9,2,10]), set([16,14,22,15]), set([7,8])]    # false

我想要一个函数,如果列表中的每个集合与列表中的至少一个其他集相交,则返回True.是否内置了这个或简单的列表理解？

Answer 1

all(any(a & b for a in s if a is not b) for b in s)

Answer 2

这是一个非常简单的解决方案,对大型输入非常有效:

def g(s):
    import collections
    count = collections.defaultdict(int)
    for a in s:
        for x in a:
            count[x] += 1
    return all(any(count[x] > 1 for x in a) for a in s)

Answer 3

这有点冗长，但我认为这是一个非常有效的解决方案。它利用了这样一个事实：当两个集合相交时，我们可以将它们标记为已连接。它通过保留与集合列表一样长的标志列表来实现这一点。当 seti和 setj相交时，它会为两者设置标志。然后，它循环遍历集合列表，并仅尝试查找尚未相交的集合的交集。读完评论后，我认为这就是@Victor 所说的。

s0 = [set([16,9,2,10]), set([16,14,22,15]), set([14,7])]   # true, 16 and 14
s1 = [set([16,9,2,10]), set([16,14,22,15]), set([7,8])]    # false


def connected(sets):
    L = len(sets)

    if not L: return True
    if L == 1: return False

    passed = [False] * L
    i = 0
    while True:
        while passed[i]: 
            i += 1
            if i == L: 
                return True

        for j, s in enumerate(sets):
            if j == i: continue
            if sets[i] & s: 
                passed[i] = passed[j] = True
                break
        else:
            return False


print connected(s0)
print connected(s1)

我决定连接一个空的集合列表（如果您生成列表的一个元素，我可以生成一个它相交的元素；）。仅包含一个元素的列表可以轻松断开连接。如果您不同意，无论哪种情况，都可以更改一行。