集合列表的减法

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

是的，它可以完成，但很难做到 pythonic

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

可以找到一些关于集合的参考资料in the documentation. The * operator is called unpacking operator。

Answer 2

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

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]

或者，不是直接从 element_counts 构造 nondupes，我们可以进行额外的传递以构造一组恰好出现在一个输入中的所有元素。这需要一个额外的语句，但它允许我们利用 & 运算符进行集合交集，使列表理解更短、更有效：

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 2 上的整个重复消除过程大约是 3.5x speedup on Python 3 for heavily-duplicate input sets, though only about a 30% speedup，因为更多的运行时间被构造计数器所支配。这种加速是相当可观的，尽管不如首先使用 element_counts 避免二次运行时间那么重要。如果你在 Python 2 上并且这段代码是速度关键的，你会想要使用普通的 dict 或 collections.defaultdict 而不是 Counter.

另一种方法是从 element_counts 构造一个 dupes 集，并在列表理解中使用 original - dupes 而不是 original & all_uniques，因为 by munk. Whether this performs better or worse than using an all_uniques set and & would depend on the degree of duplication in your input and what Python version you're on, but it doesn't seem 到无论哪种方式都有很大的不同。

Answer 3

另一个解决方案itertools.chain：

>>> from itertools import chain
>>> [x - set(chain(*(y for y in allsets if y!=x))) for x in allsets]
[set([1, 2]), set([6]), set([7])]

也可以不拆包，而是使用 chain.from_iterable。

Answer 4

使用 Counter 和理解的稍微不同的解决方案，以利用 - 运算符来设置差异。

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]

集合列表的减法

Subtraction over a list of sets

python

algorithm

list-comprehension

list

set