测试 python Counter 是否包含在另一个 Counter 中

Question

如何使用以下定义测试 python Counter 是否 包含在另一个 中：

A Counter a is contained in a Counter b if, and only if, for every key k in a, the value a[k] is less or equal to the value b[k]. The Counter({'a': 1, 'b': 1}) is contained in Counter({'a': 2, 'b': 2}) but it is not contained in Counter({'a': 2, 'c': 2}).

我认为这是一个糟糕的设计选择，但在 python 2.x 中，比较运算符（<、<= ,>=,>)不使用前面的定义，所以第三个Counter被认为大于第一个。在 python 3.x 中，Counter 是 不可排序的类型 .

Answer 1

我想出的最好办法是转换我在代码中给出的定义：

def contains(container, contained):
    return all(container[x] >= contained[x] for x in contained)

但是，如果觉得 python 没有 开箱即用的 解决方案感到奇怪，我必须为每个运算符（或制作一个通用的并通过比较功能）。

Answer 2

虽然 Counter 实例无法与 < 和 > 运算符进行比较，但您可以发现它们与 - 运算符的区别。差异永远不会 returns 负计数，因此如果 A - B 为空，则您知道 B 包含 A.

中的所有项目

def contains(larger, smaller):
    return not smaller - larger

Answer 3

对于较小 Counter 中的所有键，确保没有值大于较大 Counter 中对应的值：

def containment(big, small):
    return not any(v > big[k] for (k, v) in small.iteritems())

>>> containment(Counter({'a': 2, 'b': 2}), Counter({'a': 1, 'b': 1}))
True
>>> containment(Counter({'a': 2, 'c': 2, 'b': 3}), Counter({'a': 2, 'b': 2}))
True
>>> print containment(Counter({'a': 2, 'b': 2}), Counter({'a': 2, 'b': 2, 'c':1}))
False
>>> print containment(Counter({'a': 2, 'c': 2}), Counter({'a': 1, 'b': 1})
False

Answer 4

另一种相当简洁的表达方式：

“计数器 A 是计数器 B 的子集”等同于 (A & B) == A。

那是因为两个Counter的交集(&)有两个共同的元素个数。如果 A 的每个元素（计算多重性）也在 B 中，那将与 A 相同；否则会变小。

在性能方面，这似乎与 Blckknght 提出的 not A - B 方法大致相同。按照 enrico.bacis 的答案检查每个键要快得多。

作为变体，您还可以检查并集是否等于较大的计数器（因此未添加任何内容）：(A | B) == B。对于我测试的一些较大的多重集（1,000,000 个元素），这明显较慢。

测试 python Counter 是否包含在另一个 Counter 中

Test if python Counter is contained in another Counter

python

algorithm

counter

inclusion