Python集合交集问题
我有三个集合:
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。是否有内置的或简单的列表理解?
I have three sets:
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
I want a function that will return True if every set in the list intersects with at least one other set in the list. Is there a built-in for this or a simple list comprehension?
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(8)
这是一个非常简单的解决方案,对于大输入非常有效:
Here's a very simple solution that's very efficient for large inputs:
这有点冗长,但我认为这是一个非常有效的解决方案。它利用了这样一个事实:当两个集合相交时,我们可以将它们标记为已连接。它通过保留与集合列表一样长的标志列表来实现这一点。当设置
i
和设置j
相交时,它会为它们设置标志。然后,它循环遍历集合列表,并仅尝试查找尚未相交的集合的交集。读完评论后,我认为这就是@Victor 所说的。我决定连接一个空的集合列表(如果您生成列表的一个元素,我可以生成一个它相交的元素;)。仅包含一个元素的列表可以轻松断开连接。如果您不同意,无论哪种情况,都可以更改一行。
It's a little verbose but I think it's a pretty efficient solution. It takes advantage of the fact that when two sets intersect, we can mark them both as connected. It does this by keeping a list of flags as long as the list of sets. when set
i
and setj
intersect, it sets the flag for both of them. It then loops over the list of sets and only tries to find a intersection for sets that haven't already been intersected. After reading the comments, I think this is what @Victor was talking about.I decided that an empty list of sets is connected (If you produce an element of the list, I can produce an element that it intersects ;). A list with only one element is dis-connected trivially. It's one line to change in either case if you disagree.
这是一个更有效(如果更复杂)的解决方案,它执行线性数量的交集和数量为 O( n*log(n) ) 的并集,其中 n 是 s 的长度:
请注意,此解决方案仅适用于 Python >= 2.6。
Here's a more efficient (if much more complicated) solution, that performs a linear number of intersections and a number of unions of order O( n*log(n) ), where n is the length of
s
:Note that this solution only works on Python >= 2.6.
像往常一样,我想给出不可避免的
itertools
解决方案;-)这真的很懒,只会执行所需的交集。它也可能是一个非常令人困惑和难以阅读的单行文字;-)
As usual I'd like to give the inevitable
itertools
solution ;-)This is really lazy and will only do the intersections that are required. It can also be a very confusing and unreadable oneliner ;-)
要回答您的问题,不,没有内置或简单的列表理解可以满足您的要求。这是另一个非常高效的基于
itertools
的解决方案 - 令人惊讶的是,在计时测试中使用groupby()
的速度是 @THC4k 的itertools
答案的两倍您的样本输入。它可能还可以进一步优化,但正如所呈现的那样,它的可读性非常好。就像@AaronMcSmooth一样,当输入列表中没有或只有一组时,我任意决定返回什么。To answer your question, no, there isn't a built-in or simple list comprehension that does what you want. Here's another
itertools
based solution that is very efficient -- surprisingly about twice as fast as @THC4k'sitertools
answer usinggroupby()
in timing tests using your sample input. It could probably be optimized a bit further, but is very readable as presented. Like @AaronMcSmooth, I arbitrarily decided what to return when there are no or is only one set in the input list.此策略不太可能像@Victor的建议那么有效,但可能比 jchl 的答案 由于集合算术(
union
)的使用增加。This strategy isn't likely to be as efficient as @Victor's suggestion, but might be more efficient than jchl's answer due to increased use of set arithmetic (
union
).根据集合的分布,这可能会提供更好的性能。
This may give better performance depending on the distribution of the sets.