减去集合列表

Question

给出一组集合:

allsets = [set([1, 2, 4]), set([4, 5, 6]), set([4, 5, 7])]

什么是pythonic方法来计算与其他集不重叠的元素集的相应列表？

only = [set([1, 2]), set([6]), set([7])]

有没有办法用列表理解来做到这一点？

Answer 1

要避免二次运行时,您需要进行初始传递以确定哪些元素出现在多个集合中:

import itertools
import collections
element_counts = collections.Counter(itertools.chain.from_iterable(allsets))

然后,您只需创建一个集合列表,保留仅出现一次的所有元素:

nondupes = [{elem for elem in original if element_counts[elem] == 1}
            for original in allsets]

或者,代替构建nondupes从element_counts直接,我们可以使一个附加通构建一套出现在正好一个输入所有元件.这需要一个额外的声明,但它允许我们利用&运算符进行集合交集,以使列表理解更短,更有效:

element_counts = collections.Counter(itertools.chain.from_iterable(allsets))
all_uniques = {elem for elem, count in element_counts.items() if count == 1}
#                                                     ^ viewitems() in Python 2.7
nondupes = [original & all_uniques for original in allsets]

时间似乎表明使用all_uniques集合可以为整个重复消除过程产生大量加速.对于大量重复的输入集,它在Python 3上的速度提高了大约3.5倍,尽管在Python 2上整个重复消除过程只有大约30%的加速,因为更多的运行时由构造计数器来控制.这种加速是相当可观的,但并不像通过element_counts首先使用来避免二次运行时那么重要.如果您使用的是Python 2并且此代码对速度至关重要,那么您需要使用普通代码dict或collections.defaultdict代替a代码Counter.

另一种方法是dupes从munk中建议element_counts使用original - dupes而不是original & all_uniques在列表理解中构造一个集合.这是否执行比使用更好或更差集和将取决于重复你输入的程度,什么Python版本你,但它并不显得做出多大的差别两种方式.all_uniques&

Answer 2

是的,它可以完成,但几乎不是pythonic

>>> [(i-set.union(*[j for j in allsets if j!= i])) for i in allsets]   
[set([1, 2]), set([6]), set([7])]

可以在文档中找到有关集合的一些参考.该*操作被称为拆箱操作.

Answer 3

使用计数器和理解的稍微不同的解决方案,利用-操作员设置差异.

from itertools import chain
from collections import Counter

allsets = [{1, 2, 4}, {4, 5, 6}, {4, 5, 7}]
element_counts = Counter(chain.from_iterable(allsets))

dupes = {key for key in element_counts 
         if element_counts[key] > 1}

only = [s - dupes for s in allsets]