如何在python中快速获取集合的所有交集
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了如何在python中快速获取集合的所有交集，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2806字，纯文字阅读大概需要5分钟。
内容图文
我想在python中计算有限整数集合(这里实现为列表列表)的所有(不同)交集(为了避免混淆,正式定义在问题的最后)：
> A = [[0,1,2,3],[0,1,4],[1,2,4],[2,3,4],[0,3,4]]
> all_intersections(A) # desired output
[[], [0], [1], [2], [3], [4], [0, 1], [0, 3], [0, 4], [1, 2], [1, 4], [2, 3], [2, 4], [3, 4], [0, 1, 4], [0, 3, 4], [1, 2, 4], [2, 3, 4], [0, 1, 2, 3]]
我有一个迭代执行它的算法,但它相当慢(我应该发布吗？),一个测试用例
[[0, 1, 2, 3, 4, 9], [0, 1, 4, 5, 6, 10], [0, 2, 4, 5, 7, 11], [1, 3, 4, 6, 8, 12], [2, 3, 4, 7, 8, 13], [4, 5, 6, 7, 8, 14], [0, 1, 9, 10, 15, 16], [0, 2, 9, 11, 15, 17], [1, 3, 9, 12, 16, 18], [2, 3, 9, 13, 17, 18], [9, 15, 16, 17, 18, 19], [0, 5, 10, 11, 15, 20], [1, 6, 10, 12, 16, 21], [10, 15, 16, 19, 20, 21], [5, 6, 10, 14, 20, 21], [11, 15, 17, 19, 20, 22], [5, 7, 11, 14, 20, 22], [2, 7, 11, 13, 17, 22], [7, 8, 13, 14, 22, 23], [3, 8, 12, 13, 18, 23], [13, 17, 18, 19, 22, 23], [14, 19, 20, 21, 22, 23], [6, 8, 12, 14, 21, 23], [12, 16, 18, 19, 21, 23]]
这需要我大约2.5秒来计算.
Any ideas how to do it fast?
正式定义(实际上没有乳胶模式很难)：让A = {A1,…,An}是非负整数的有限集合Ai的有限集合.然后输出应该是集合{A的B：B子集中的集合的交集}.
因此,正式算法将采用A的所有子集的所有交叉点的并集.但这显然是永远的.
非常感谢！
解决方法:
这是一个递归解决方案.在您的测试示例中几乎是即时的：
def allIntersections(frozenSets):
if len(frozenSets) == 0:
return []
else:
head = frozenSets[0]
tail = frozenSets[1:]
tailIntersections = allIntersections(tail)
newIntersections = [head]
newIntersections.extend(tailIntersections)
newIntersections.extend(head & s for s in tailIntersections)
return list(set(newIntersections))
def all_intersections(lists):
sets = allIntersections([frozenset(s) for s in lists])
return [list(s) for s in sets]
在编辑这里是一个更清晰,非递归的相同想法的实现.
如果将空集合的集合定义为通用集合,则问题最容易,并且可以通过获取所有元素的并集来获得足够的通用集合.这是格理论中的标准运动,并且将空集合的集合作为空集合是双重的.如果你不想要它,你总是可以抛弃这个通用集：
def allIntersections(frozenSets):
universalSet = frozenset.union(*frozenSets)
intersections = set([universalSet])
for s in frozenSets:
moreIntersections = set(s & t for t in intersections)
intersections.update(moreIntersections)
return intersections
def all_intersections(lists):
sets = allIntersections([frozenset(s) for s in lists])
return [list(s) for s in sets]
您的测试示例如此之快的原因在于,即使您的集合有24集,因此有2 ** 24(1680万)个潜在交叉点,实际上只有242个(如果不计算则为241个)空的交叉点)不同的交叉点.因此,每次通过循环的交叉点的数量最多为数百.
可以选择24组,以便所有2 ** 24个可能的交叉点实际上是不同的,因此很容易看出最坏情况的行为是指数的.但是,如果在测试示例中,交叉点的数量很少,则此方法将允许您快速计算它们.
潜在的优化可能是在循环之前对集合的大小进行排序.前面处理较小的设置可能导致更早出现的空交叉点,从而使不同交叉点的总数保持较小,直到循环结束.
内容总结
以上是互联网集市为您收集整理的如何在python中快速获取集合的所有交集全部内容，希望文章能够帮你解决如何在python中快速获取集合的所有交集所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。