7

我有三套:

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 的函数。是否有内置的或简单的列表理解?

4

8 回答 8

14
all(any(a & b for a in s if a is not b) for b in s)
于 2010-10-01T08:32:24.407 回答
5

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

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)
于 2010-10-01T12:50:22.623 回答
2

这有点冗长,但我认为这是一个非常有效的解决方案。它利用了当两个集合相交时,我们可以将它们都标记为已连接的事实。它通过保持与集合列表一样长的标志列表来做到这一点。当设置i和设置j相交时,它为它们设置标志。然后它遍历集合列表,只尝试为尚未相交的集合寻找交集。阅读评论后,我认为这就是@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)

我决定连接一个空的集合列表(如果您生成列表的一个元素,我可以生成一个它相交的元素;)。只有一个元素的列表很容易断开连接。如果您不同意,则在任何一种情况下都可以更改。

于 2010-10-01T08:27:43.820 回答
2

这是一个更有效(如果更复杂)的解决方案,它执行线性数量的交叉点和 O( n*log(n) ) 阶的多个并集,其中 n 是 的长度s

def f(s):
    import math
    j = int(math.log(len(s) - 1, 2)) + 1
    unions = [set()] * (j + 1)
    for i, a in enumerate(s):
        unions[:j] = [set.union(set(), *s[i+2**k:i+2**(k+1)]) for k in range(j)]
        if not (a & set.union(*unions)):
            return False
        j = int(math.log(i ^ (i + 1), 2))
        unions[j] = set.union(a, *unions[:j])
    return True

请注意,此解决方案仅适用于 Python >= 2.6。

于 2010-10-01T11:23:54.413 回答
1

像往常一样,我想给出不可避免的itertools解决方案;-)

from itertools import combinations, groupby
from operator import itemgetter


def any_intersects( sets ):
    # we are doing stuff with combinations of sets
    combined = combinations(sets,2) 
    # group these combinations by their first set
    grouped = (g for k,g in groupby( combined, key=itemgetter(0)))
    # are any intersections in each group
    intersected = (any((a&b) for a,b in group) for group in grouped)
    return all( intersected )


s0 = [set([16,9,2,10]), set([16,14,22,15]), set([14,7])]
s1 = [set([16,9,2,10]), set([16,14,22,15]), set([7,8])] 
print any_intersects( s0 ) # True
print any_intersects( s1 ) # False

这真的很懒惰,只会做需要的交叉点。它也可能是一个非常混乱和不可读的单行线;-)

于 2010-10-01T13:18:06.460 回答
1

要回答您的问题,不,没有内置或简单的列表理解可以满足您的需求。这是另一个非常有效的基于解决方案的解决方案——令人惊讶的是,在使用您的样本输入进行计时测试时,它的速度是@THC4k答案itertools的两倍。它可能会进一步优化,但呈现出来的可读性很强。像@AaronMcSmooth 一样,我任意决定在输入列表中没有或只有一组时返回什么。itertoolsgroupby()

from itertools import combinations

def all_intersect(sets):
    N = len(sets)
    if not N: return True
    if N == 1: return False

    intersected = [False] * N
    for i,j in combinations(xrange(N), 2):
        if not intersected[i] or not intersected[j]:
            if sets[i] & sets[j]:
                intersected[i] = intersected[j] = True
    return all(intersected)
于 2010-10-01T14:22:32.667 回答
0

这种策略可能不像@Victor 的建议那样有效,但由于增加了对集合算术 ( )的使用,它可能比jchl 的答案更有效。union

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

def freeze(list_of_sets):
    """Transform a list of sets into a frozenset of frozensets."""
    return frozenset(frozenset(set_) for set_ in list_of_sets)

def all_sets_have_relatives(set_of_sets):
    """Check if all sets have another set that they intersect with.

    >>> all_sets_have_relatives(s0)   # true, 16 and 14
    True
    >>> all_sets_have_relatives(s1)   # false
    False
    """
    set_of_sets = freeze(set_of_sets)
    def has_relative(set_):
        return set_ & frozenset.union(*(set_of_sets - set((set_,))))
    return all(has_relative(set) for set in set_of_sets)
于 2010-10-01T09:30:01.080 回答
0

根据集合的分布,这可能会提供更好的性能。

def all_intersect(s):
   count = 0
   for x, a in enumerate(s):
      for y, b in enumerate(s):
         if a & b and x!=y:
            count += 1
            break
   return count == len(s)
于 2010-10-01T10:44:38.507 回答