Python集合交集问题

Question

Python集合交集问题

6

我有三个集合：

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。是否有内置函数或简单的列表推导可用？

- Eric Schoonover

8个回答

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)

- jchl

你可以使用count.setdefault(x, 0) += 1代替if/else语句。 - aaronasterling

1

不可以。count.setdefault(x, 0)不是一个左值。 - jchl

1

+1 是因为它规避了“显而易见”的集合交集问题并简化了问题。不幸的是，我认为你不会得到足够的赞。顺便说一下，要么使用collections.Counter，要么使用count= collections.defaultdict(int)和count[x]+=1。 - tzot

谢谢你提到了defaultdict。我已经相应地简化了我的答案。 - jchl

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)

我认为空集列表是连通的（如果您产生了该列表的一个元素，我可以生成它相交的元素;)。只有一个元素的列表是不连通的，这是显而易见的。无论哪种情况下都只需要更改一行代码，如果您不同意，请告知。

- aaronasterling

有很多好的答案，我现在正在使用2.5.2，所以最终选择了这个解决方案。 - Eric Schoonover

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 版本。

- jchl

这个方案的性能明显比你之前的答案慢得多。而你之前的答案平均需要4.7毫秒（在大量随机输入的情况下），而这个方案需要250毫秒。联合体是导致性能问题的罪魁祸首（在这个实现中）并且很费解。从理论上讲很有吸引力，但代价高昂。 - aaronasterling

有趣。我认为这是由于所有Python代码的大常数因素（与几乎可以全部在C中评估的先前解决方案相比）。此外，如果any()调用经常进行快捷方式，则我的第一个解决方案将很好地工作，而这个解决方案在所有情况下都很有效。对于此输入，此解决方案的性能优于第一个解决方案（9秒对24秒）：[set((i,)) for i in range(N)] + [set(range(N))]，其中N = 10000，我怀疑在更大的N下仍然会表现得更好。 - jchl

我刚意识到这个解决方案比必要的要复杂得多，而且仍然不是最优的。我的第三个解决方案在这两个方面都更好。 - jchl

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

这真的很懒，只会做必需的交集。它也可能是一个非常混乱和难以阅读的一行代码；-）

- Jochen Ritzel

组合？那“combined”呢？;-) - martineau

嘿，一些在线词典列出了“combinated”，但“combined”听起来更好一些;-) - Jochen Ritzel

进一步思考后，“combos”可能是一个更具描述性的变量名称，因此更好。 - martineau

1

回答你的问题，没有内置或简单的列表推导式可以做到你想要的。这里有另一个基于itertools的解决方案，非常高效--在使用你的示例输入进行定时测试时，令人惊讶地比@THC4k使用groupby()的itertools答案快了约两倍。它可能还可以进一步优化，但是按照现有的方式非常易读。像@AaronMcSmooth一样，我随意决定了在输入列表中没有或只有一个集合时返回什么。

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)

- martineau

0

这种策略可能不像@Victor的建议那样高效，但由于更多地使用了集合运算（union），它可能比jchl's answer更高效。

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)

- intuited

@jchl：集合不可哈希，因此不能作为集合中的元素。我不确定将顶层集合设置为frozen集合是否有太多意义，但它似乎比常规集合更快，并且符合逻辑。 - intuited

@jchl：啊，现在我知道你在说什么了。看起来我在重构和发布那段代码时遇到了某种精神消化问题。“不过doctest通过了！”无论如何，现在已经修复了。 - intuited

我的分析表明它们稍微快一点，虽然只是勉强的。 - aaronasterling

坏消息。我刚对这个进行了性能分析，发现它运行时间约为2.5秒，在与@jchl相同类型的大型随机输入上，@jchl只需4.7毫秒。对于我来说，坏消息是，虽然我付出了所有的努力，但我只比他快了0.2毫秒。 - aaronasterling

哦！我被杀了！有趣...是使用大数据集还是很多数据集，还是两者都有？ - intuited

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)

- dheerosaur

2

你的意思是用break而不是continue吧？
count = -1这样写没问题吗？
删除第二行，将最后3行替换为return count == len(s)。
如果写成x != y and a & b会更好吧？
如果一个集合没有"buddies"，你并没有提前退出，那么什么是“可能会有更好的性能”的基础？比什么更好？

- John Machin

1

你好，你好，...你的代码出问题了。count成为非空两两集合交集的数量，减1。这与OP想要的完全不同。偶然情况下，它可以给出OP的两个测试用例的正确答案。试试这个：s2 = [set([16, 9, 2, 10]), set([16, 22, 14, 15]), set([14, 2])] ... 它应该返回True，但是你的计数是6-1 == 5，所以你的代码返回False。 - John Machin

@John，+1，感谢您指出所有错误。我已经进行了编辑以进行所有必要的更正。4. 我更喜欢使用a＆b而不是x！= y，因为后者更常见。这样做有问题吗？5. 是的，没错。与对所有集合进行交集检查的方法相比，这可能会提供更好的性能。 - dheerosaur

检查 x != y 的整个目的是避免为 a is b 计算 a & b。重点是检查 x != y 要比执行集合交集便宜得多。 - aaronasterling

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- jchl · Accepted Answer

14

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

- jchl

2

优雅，但我更喜欢使用两个直接的循环和一个计数器来避免每次比较两个项目两次，这将至少加快两倍速度。 - Victor Ionescu

bool() 调用是多余的。 - kennytm

1

@spoon16：我尝试去除不必要的比较。当然，由于额外的代码，我不确定这是否会得到一个优化过的版本，相比jchl提供的相当优雅的解决方案。我可能会尝试在一个大型序列上对两者进行计时，看看结果如何。 - pyfunc

@KennyTM：谢谢，我没有意识到any()执行自动布尔转换。我删除了bool()调用。 - jchl

我认为在存在两个相同集合的情况下，这可能会出现一些问题。例如：set(())不等于set(())。 - intuited

显示剩余3条评论