Python3 找出两个列表中有多少差异才能相等

Question

假设我们有 2 个列表，always 具有相同的长度，always 包含字符串。

list1 = ['sot', 'sot', 'ts', 'gg', 'gg', 'gg']
list2 = ['gg', 'gg', 'gg', 'gg', 'gg', 'sot']

我们需要找到：

为了与 list1 相等，list2 应更改多少项。

所以在前面的例子中它应该 return 2

对于这个例子：

list1 = ['sot', 'sot', 'ts', 'gg', 'gg', 'gg']
list2 = ['gg', 'gg', 'gg', 'gg', 'sot', 'sot']

应该return1

最后是这个例子：

list1 = ['sot', 'sot', 'ts', 'gg', 'gg', 'gg']
list2 = ['ts', 'ts', 'ts', 'ts', 'ts', 'ts']

应该return5.

我们不关心哪些元素应该变成什么。我们都不关心顺序，所以这意味着

['gg', 'gg', 'gg', 'gg', 'gg', 'sot'] 
and
['gg', 'gg', 'sot', 'gg', 'gg', 'gg']

相等，结果应该为0。

列表的长度可以是 6、8、20 或其他，有时会有更多元素。

我尝试了很多方法，例如 set(list1) - set(list2) 、list(set(list1).difference(list2)) 、 set(list1).symmetric_difference(set(list2)) 但都没有成功。

Answer 1

您可以为此使用 collections.Counter，计算两个列表中的项目数，然后计算它们之间的差值。

from collections import Counter
def func(list1, list2):
    #Convert both list to counters, and subtract them
    c = Counter(list1) - Counter(list2)

    #Sum up all values in the new counter
    return sum(c.values())

输出是

list1 = ['sot', 'sot', 'ts', 'gg', 'gg', 'gg']
list2 = ['gg', 'gg', 'gg', 'gg', 'gg', 'sot']
print(func(list1, list2))
#2

list1 = ['sot', 'sot', 'ts', 'gg', 'gg', 'gg']
list2 = ['gg', 'gg', 'gg', 'gg', 'sot', 'sot']
print(func(list1, list2))
#1

list1 = ['sot', 'sot', 'ts', 'gg', 'gg', 'gg']
list2 = ['ts', 'ts', 'ts', 'ts', 'ts', 'ts']
print(func(list1, list2))
#5

Answer 2

如果差异在于多少存在某个项目，则使用set 会导致问题。相反，请使用 collections.Counter。正如其他答案中所解释的，您可以为两个列表创建一个 Counter，然后使用 - 来获得它们的差异并获得 values 的 sum。但是请注意，如果列表的大小相同，这将仅起作用。如果列表没有相同数量的元素，您将得到不同数量的发散元素，具体取决于从哪个列表中减去哪个列表。

另一方面，

使用 subtract，您将在两个方向上得到差异，对 "too many" 负数的项目使用正数"too few"。这意味着，您可能必须将结果除以 2，即 sum(...) / 2，但它对于不同大小的列表应该更有效。

>>> list1 = ['sot', 'sot', 'ts', 'gg', 'gg', 'gg']
>>> list2 = ['gg', 'gg', 'gg', 'gg', 'sot', 'sot']
>>> c = Counter(list1)
>>> c.subtract(Counter(list2))
# Counter({'gg': -1, 'sot': 0, 'ts': 1})
>>> sum(map(abs, c.values()))
2

另一种对不同大小的列表也能可靠工作的可能性是使用 & 获取 common 元素，然后将这些元素与列表中的元素总数进行比较更大的列表：

>>> list1 = [1,1,1,1,2]
>>> list2 = [2]
>>> Counter(list1) & Counter(list2)
Counter({2: 1})
>>> max(len(list1), len(list2)) - sum((Counter(list1) & Counter(list2)).values())
4

Answer 3

您可以利用 Counter 提供的多种可能性：

list1 = ['sot', 'sot', 'ts', 'gg', 'gg', 'gg']
list2 = ['gg', 'gg', 'gg', 'gg', 'gg', 'sot']

from collections import Counter

sum((Counter(list1) - Counter(list2)).values())
# 2

让我们检查其他示例：

list1 = ['sot', 'sot', 'ts', 'gg', 'gg', 'gg']
list2 = ['gg', 'gg', 'gg', 'gg', 'sot', 'sot']

sum((Counter(list1) - Counter(list2)).values())
# 1

list1 = ['sot', 'sot', 'ts', 'gg', 'gg', 'gg']
list2 = ['ts', 'ts', 'ts', 'ts', 'ts', 'ts']

sum((Counter(list1) - Counter(list2)).values())
# 5

list1 = ['gg', 'gg', 'gg', 'gg', 'gg', 'sot'] 
list2 = ['gg', 'gg', 'sot', 'gg', 'gg', 'gg']

sum((Counter(list1) - Counter(list2)).values())
# 0

详情

通过使用 Counter，您将以字典的形式计算每个列表中的所有元素。让我们回到第一个例子：

c1 = Counter(list1)
# Counter({'sot': 2, 'ts': 1, 'gg': 3})

c2 = Counter(list2)
# Counter({'gg': 5, 'sot': 1})

现在我们想以某种方式了解：

哪些项目出现在 list1 但不出现在 list2
在存在的和不存在的那些中，list2 还需要多少个才能使它们包含相同数量的计数

好吧，我们可以利用计数器支持数学运算这一事实，其结果会产生 multisets，即计数大于零的计数器。因此，鉴于我们正在寻找两个计数器之间的差异，似乎我们可以减去它们并查看 list2 中需要哪些元素及其各自的计数。

那么计数器之间的减法如何工作？让我们看一个简单的例子：

Counter({1:4, 2: 1}) - Counter({1:1, 3:1})  
# Counter({1: 3, 2: 1})

所以这里做的是减去相应元素的计数，所以第一个计数器中包含的元素，因此这里的顺序很重要。所以回到提议的例子，减去两个列表会产生：

 sub = Counter(list1) - Counter(list2)
# Counter({'sot': 1, 'ts': 1})

现在我们简单地需要计算所有keys中的values，这可以通过：

来完成

sum(sub.values())
# 2

Answer 4

你在这里不是在谈论列表。您的问题是 multiset problem，因为顺序无关紧要，但您确实需要知道每种类型有多少个值。 Multisets 有时称为 bags 或 msets.

Python 标准库有一个多重集实现：collections.Counter()，它将唯一元素映射到一个计数。在这里使用它们：

from collections import Counter

mset1 = Counter(list1)
mset2 = Counter(list2)

# sum the total number of elements that are different between
# the two multisets
sum((mset1 - mset2).values())

从另一个计数器中减去一个计数器得到一个多重集，其中包含第一个多重集中但不在另一个多重集中的所有元素，sum(mset.values()) 加起来就是元素总数。

因为输入总是相同的长度，而您只需要知道有多少元素不同，所以没关系您减去多重集的顺序。您将始终得到正确答案，sum((mset1 - mset2).values()) 和 sum((mset2 - mset1).values()) 将始终产生完全相同的数字。

那是因为两个multiset都有N个元素，其中K个不同。因此，两个多重集都将恰好有 K extra 个元素不在另一个多重集中，并且有 K missing 个元素存在于另一个集合中。 - 减法会给你 K 个额外的元素在第一组中，而在另一组中缺失。

将其放入函数中：

def mset_diff(iterable1, iterable2):
    return sum((Counter(iterable1) - Counter(iterable2)).values())

并应用于您的输入：

>>> mset_diff(['sot', 'sot', 'ts', 'gg', 'gg', 'gg'], ['gg', 'gg', 'gg', 'gg', 'gg', 'sot'])
2
>>> mset_diff(['sot', 'sot', 'ts', 'gg', 'gg', 'gg'], ['gg', 'gg', 'gg', 'gg', 'sot', 'sot'])
1
>>> mset_diff(['sot', 'sot', 'ts', 'gg', 'gg', 'gg'], ['ts', 'ts', 'ts', 'ts', 'ts', 'ts'])
5

Counter() class 是 dict 的子class，计数元素快速高效，计算两者之间的差异在 O(N ) 线性时间。

Python3 找出两个列表中有多少差异才能相等

Python3 find how many differences are in 2 lists in order to be equal

python

list

multiset

python-3.x