寻找两个Python列表之间的“重叠”部分。

Question

给出两个列表：

a = [3,4,5,5,5,6]
b = [1,3,4,4,5,5,6,7]

我想找到“overlap”：

c = [3,4,5,5,6]

如果可能的话，我还希望能够提取出a和b中不属于c的“剩余部分”。

a_remainder = [5,]
b_remainder = [1,4,7,]

注意：a 中有三个 5，b 中有两个。 a 中只有一个 4，而 b 中有两个。 结果列表 c 应该包含两个 5（受 b 列表限制）和一个 4（受 a 列表限制）。

这给了我想要的结果，但我不禁觉得可能有更好的方法。

import copy

a = [3,4,5,5,5,6]
b = [1,3,4,4,5,5,6,7]

c = []
for elem in copy.deepcopy(a):
    if elem in b:
        a.pop(a.index(elem))
        c.append(b.pop(b.index(elem)))

# now a and b both contain the "remainders" and c contains the "overlap"

在另一个方面，除了“overlap”和“remainder”，有没有更准确的名称来描述我所询问的内容？

- user625477

---

在集合论中，"overlap" 被称为交集，而 "remainder" 被称为差集。不幸的是，由于存在重复值，使用 Python 集合无法在一行代码中完成这些操作。 - nmichaels

你可以在这里使用 list(a) 代替 copy.deepcopy(a)。 - Rosh Oxymoron

应该是 a_remainder = [5,]，对吧？ - Andrew Jaffe

你也可以使用 a[:] 替代 copy.deepcopy(a)。 - nmichaels

Andrew Jaffe：你说得对。我会调整问题，以避免其他人的困惑。 - user625477

nmichaels和Rosh Oxymoron：谢谢。我觉得那很蠢，但不确定该如何处理。 - user625477

Answer 1

Python 2.7中提供了collection.Counter，可以用来实现多重集合，完全符合你的需求。

a = [3,4,5,5,5,6]
b = [1,3,4,4,5,5,6,7]

a_multiset = collections.Counter(a)
b_multiset = collections.Counter(b)

overlap = list((a_multiset & b_multiset).elements())
a_remainder = list((a_multiset - b_multiset).elements())
b_remainder = list((b_multiset - a_multiset).elements())

print overlap, a_remainder, b_remainder

- Rosh Oxymoron

Answer 2

使用Python集合(set)

intersection = set(a) & set(b)
a_remainder = set(a) - set(b)
b_remainder = set(b) - set(a)

- kefeizhou

---

这是一个不错的想法，但是该人的数据不是有效的集合，存在重复项，也需要考虑到这一点。 - eapen

Answer 3

在集合语言中，重叠部分是“交集”，剩余部分是“差集”。如果您有不同的项目，就不必自己执行这些操作，请查看http://docs.python.org/library/sets.html 了解更多信息。

由于我们没有使用不同的元素，所以您的方法是合理的。如果您想使其运行更快，可以为每个列表创建一个字典，并将数字映射到每个数组中的元素数（例如，在a中，3->1，4->1，5->2等）。然后，您将遍历map a，确定该字母是否存在，减少其计数并将其添加到新列表中。

未经测试的代码，但这就是思路。

def add_or_update(map,value):
    if value in map:
        map[value]+=1
    else
        map[value]=1

b_dict = dict()
for b_elem in b:
    add_or_update(b_dict,b_elem)

intersect = []; diff = [];

for a_elem in a:
    if a_elem in b_dict and b_dict[a_elem]>0:
        intersect.add(a_elem);

for k,v in diff:
    for i in range(v):
        diff.add(k);

- dfb

Answer 4

好的，冗长一些，但有点酷（类似于collections.Counter的思路，但更自制）：

import itertools as it
flatten = it.chain.from_iterable 
sorted(
   v for u,v in 
    set(flatten(enumerate(g) 
        for k, g in it.groupby(a))).intersection(
    set(flatten(enumerate(g)
        for k, g in it.groupby(b))))
   )

基本思路是将每个列表转换为一个新的列表，其中每个对象都附带一个计数器，以考虑重复项 - 这样你就可以在所有元组上使用set操作了。

稍微简洁一些：

 aa = set(flatten(enumerate(g) for k, g in it.groupby(a)))
 bb = set(flatten(enumerate(g) for k, g in it.groupby(b)))
 # aa = set([(0, 3), (0, 4), (0, 5), (0, 6), (1, 5), (2, 5)])
 # bb = set([(0, 1), (0, 3), (0, 4), (0, 5), (0, 6), (0, 7), (1, 4), (1, 5)])

 cc = aa.intersection(bb)
 # cc = set([(0, 3), (0, 4), (0, 5), (0, 6), (1, 5)])
 c = sorted(v for u,v in cc)
 # c = [3, 4, 5, 5, 6]

• groupby -- 产生一个由相同元素组成的列表的列表（但是因为语法需要 g for k,g in it.groupby(a) 来提取每个列表）
• enumerate -- 将计数器附加到每个子列表的每个元素上
• flatten -- 创建一个单一的列表
• set -- 转换为一个集合
• intersection -- 找出共同的元素
• sorted(v for u,v in cc) -- 去掉计数器并排序结果

最后，我不确定您指的是什么余数；看起来应该是我的 aa-cc 和 bb-cc，但我不知道您从哪里得到 a_remainder = [4]：

sorted(v for u,v in aa-cc)
# [5]

sorted(v for u,v in bb-cc)
# [1, 4, 7]

- Andrew Jaffe

Answer 5

在freenode上的#python频道中，来自Kerio的回复如下：

[ i for i in itertools.chain.from_iterable([k] * v for k, v in \
  (Counter(a) & Counter(b)).iteritems())
]

- user625477

Answer 6

尝试使用difflib.SequenceMatcher()，它是一个灵活的类，可用于比较任何类型的序列对...

快速尝试：

a = [3,4,5,5,5,6]
b = [1,3,4,4,5,5,6,7]

sm = difflib.SequenceMatcher(None, a, b)
c = []
a_remainder = []
b_remainder = []

for tag, i1, i2, j1, j2 in sm.get_opcodes():
    if tag == 'replace':
        a_remainder.extend(a[i1:i2])
        b_remainder.extend(b[j1:j2])
    elif tag == 'delete':
        a_remainder.extend(a[i1:i2])
    elif tag == 'insert':
        b_remainder.extend(b[j1:j2])
    elif tag == 'equal':
        c.extend(a[i1:i2])

现在...

>>> print c
[3, 4, 5, 5, 6]
>>> print a_remainder
[5]
>>> print b_remainder
[1, 4, 7]

- Steven

Answer 7

Aset = Set(a);
Bset = Set(b);
a_remainder = a.difference(b);
b_remainder = b.difference(a);
c = a.intersection(b);

但如果你需要 c 有重复项，并且顺序对你很重要，
你可以寻找 w:最长公共子序列问题。

- kirilloid

---

我不知道为什么这被踩了。这对我有用。 - KarthikS

Answer 8

我不认为你应该真的使用这个解决方案，但是我抓住了这个机会练习lambda函数，这是我得出的结果 :)

a = [3,4,5,5,5,6]
b = [1,3,4,4,5,5,6,7]
dedup = lambda x: [set(x)] if len(set(x)) == len(x) else [set(x)] + dedup([x[i] for i in range(1, len(x)) if x[i] == x[i-1]])
default_set = lambda x: (set() if x[0] is None else x[0], set() if x[1] is None else x[1])
deduped = map(default_set, map(None, dedup(a), dedup(b)))
get_result = lambda f: reduce(lambda x, y: list(x) + list(y), map(lambda x: f(x[0], x[1]), deduped))
c = get_result(lambda x, y: x.intersection(y))          # [3, 4, 5, 6, 5]
a_remainder = get_result(lambda x, y: x.difference(y))  # [5]
b_remainder = get_result(lambda x, y: y.difference(x))  # [1, 7, 4]

我相信 izip_longest 可以简化这个过程（不需要 default_set lambda 函数），但是我在 Python 2.5 中测试了它。

以下是一些计算中使用的中间值，以便任何人都可以理解：

dedup(a) = [set([3, 4, 5, 6]), set([5]), set([5])]
dedup(b) = [set([1, 3, 4, 5, 6, 7]), set([4, 5])]
deduped = [(set([3, 4, 5, 6]), set([1, 3, 4, 5, 6, 7])), (set([5]), set([4, 5])), (set([5]), set([]))]

- Andrew Clark

---

出于好奇，为什么要踩我？与其他被踩的答案不同，我的答案提供了正确的解决方案。我知道它很难阅读，但这就是免责声明存在的原因。我发布这个答案只是因为我认为其他人可能会对使用集合操作的解决方案感兴趣，即使它有点晦涩。 - Andrew Clark

只有在您可以独立验证解决方案时，它才是正确的。否则，您就要依赖作者和您能够想到的少数示例来测试它。您的解决方案对读者来说是一种很好的思维锻炼，但您不希望代码验证阶段比编写代码阶段更长。;) - Rosh Oxymoron