找到两个嵌套列表的交集？

Question

我知道如何获取两个平面列表的交集：

b1 = [1,2,3,4,5,9,11,15]
b2 = [4,5,6,7,8]
b3 = [val for val in b1 if val in b2]

或者

def intersect(a, b):
    return list(set(a) & set(b))
 
print intersect(b1, b2)

但是当我需要为嵌套列表查找交集时，我的问题就开始了：

c1 = [1, 6, 7, 10, 13, 28, 32, 41, 58, 63]
c2 = [[13, 17, 18, 21, 32], [7, 11, 13, 14, 28], [1, 5, 6, 8, 15, 16]]

最终我希望收到：

c3 = [[13,32],[7,13,28],[1,6]]

你们能帮我一下吗？

相关

• 如何在Python中扁平化一个浅层嵌套列表

- elfuego1

---

你对于 c1 和 c2 的交集会是什么？你只是想找出 c1 是否在 c2 中吗？还是你想找出 c1 中出现在 c2 中的所有元素？ - Brian R. Bondy

阅读这个并在解释器中操作。 - Pithikos

Answer 1

您无需定义交集。它已经是集合的一级部分。

>>> b1 = [1,2,3,4,5,9,11,15]
>>> b2 = [4,5,6,7,8]
>>> set(b1).intersection(b2)
set([4, 5])

- S.Lott

---

因为要转换成集合，所以这个方法会比 Lambda 慢吗？ - Ciro Santilli OurBigBook.com

set(b1) & set(b2) 有什么问题吗，@S.Lott？我认为使用运算符更加简洁。 - jds

此外，使用set将导致代码运行速度快数个数量级。以下是一个样本基准测试®:https://gist.github.com/andersonvom/4d7e551b4c0418de3160 - andersonvom

仅适用于结果不需要有序的情况。 - Borbag

所以……这个答案并没有回答问题，对吧？因为它无法处理嵌套列表。 - Mayou36

Answer 2

如果你想：

c1 = [1, 6, 7, 10, 13, 28, 32, 41, 58, 63]
c2 = [[13, 17, 18, 21, 32], [7, 11, 13, 14, 28], [1, 5, 6, 8, 15, 16]]
c3 = [[13, 32], [7, 13, 28], [1,6]]

那么这就是你在Python 2下的解决方案：

c3 = [filter(lambda x: x in c1, sublist) for sublist in c2]

在Python 3中，filter返回一个可迭代对象而不是列表，因此您需要使用list()将filter调用包装起来：

c3 = [list(filter(lambda x: x in c1, sublist)) for sublist in c2]

解释：

过滤器部分获取每个子列表的项，并检查它是否在源列表c1中。 列表推导式对c2中的每个子列表执行。

- Brian R. Bondy

---

你可以使用 filter(set(c1).__contains__, sublist) 来提高效率。顺便说一下，这种解决方案的优点是 filter() 可以保留字符串和元组类型。 - jfs

我喜欢这种方法，但我的结果列表中出现了空白''。 - Jonathan Ong

我在这里添加了Python 3兼容性，因为我将其用作Python 3问题的重复目标的副本的重复项。 - Antti Haapala -- Слава Україні

在我看来，使用嵌套推导表达式更易读：c3 = [[x for x in sublist if x in c1] for sublist in c2]。 - Eric

Answer 3

对于只想找到两个列表的交集的人，提问者提供了两种方法:

b1 = [1,2,3,4,5,9,11,15]
b2 = [4,5,6,7,8]
b3 = [val for val in b1 if val in b2]

和

def intersect(a, b):
     return list(set(a) & set(b))

print intersect(b1, b2)

但是有一种混合方法更加高效，因为你只需要在列表和集合之间进行一次转换，而不是三次转换：

b1 = [1,2,3,4,5]
b2 = [3,4,5,6]
s2 = set(b2)
b3 = [val for val in b1 if val in s2]

使用这种方法的时间复杂度为O(n)，而使用列表推导式的原始方法的时间复杂度为O(n^2)。

- Zack Burt

---

由于“if val in s2”的时间复杂度为O(N)，所以建议的代码片段复杂度也是O(n^2)。 - Unicorn

根据https://wiki.python.org/moin/TimeComplexity#set，"val in s2"的平均情况是O(1)，因此在n次操作中，预期时间为O(n)（最坏情况下的时间复杂度是O(n)或O(n^2)，这取决于平均情况是否代表分摊时间，但在实践中这并不是非常重要）。 - Chiara Coetzee

运行时间为O(N)并不是因为它被摊销了，而是因为集合成员的平均时间复杂度为O(1)（例如使用哈希表时），这是一个很大的区别，例如因为摊销时间是有保证的。 - miroB

Answer 4

函数式编程方法：

input_list = [[1, 2, 3, 4, 5], [2, 3, 4, 5, 6], [3, 4, 5, 6, 7]]

result = reduce(set.intersection, map(set, input_list))

它可以应用于更一般的情况，即1个以上的列表。

- pufferfish

---

允许空输入列表的写法为：set(*input_list[:1]).intersection(*input_list[1:])。使用迭代器的写法为(it = iter(input_list))：reduce(set.intersection, it, set(next(it, [])))。这两种写法都不需要将所有的输入列表转换为集合，后一种写法更加节省内存。 - jfs

使用from functools import reduce在Python 3中使用它。或者更好的方法是，使用显式的for循环。 - TrigonaMinima

Answer 5

纯列表推导式版本

>>> c1 = [1, 6, 7, 10, 13, 28, 32, 41, 58, 63]
>>> c2 = [[13, 17, 18, 21, 32], [7, 11, 13, 14, 28], [1, 5, 6, 8, 15, 16]]
>>> c1set = frozenset(c1)

扁平化变体：

>>> [n for lst in c2 for n in lst if n in c1set]
[13, 32, 7, 13, 28, 1, 6]

嵌套变体：

>>> [[n for n in lst if n in c1set] for lst in c2]
[[13, 32], [7, 13, 28], [1, 6]]

- J.F. Sebastian

Answer 6

& 运算符取两个集合的交集。

{1, 2, 3} & {2, 3, 4}
Out[1]: {2, 3}

- aflaisler

---

好的，但是这个话题是关于列表的！ - Rafa0809

两个列表的交集结果是一个集合，因此这个答案是完全正确的。 - shrewmouse

列表可以包含重复的值，但集合不行。 - diewland

Answer 7

获取两个列表的交集的 Pythonic 方式是：

[x for x in list1 if x in list2]

- Flying_ostrich

---

这个问题涉及到嵌套列表。你的回答并没有回答这个问题。 - Thomas

Answer 8

自从定义了intersect，一个基本的列表推导就足够了：

>>> c3 = [intersect(c1, i) for i in c2]
>>> c3
[[32, 13], [28, 13, 7], [1, 6]]

感谢S. Lott和TM的建议，改进如下：

>>> c3 = [list(set(c1).intersection(i)) for i in c2]
>>> c3
[[32, 13], [28, 13, 7], [1, 6]]

- Emmanuel

Answer 9

您应该使用以下代码（取自http://kogs-www.informatik.uni-hamburg.de/~meine/python_tricks），对其进行平铺。 代码未经测试，但我非常确定它可以工作：

def flatten(x):
    """flatten(sequence) -> list

    Returns a single, flat list which contains all elements retrieved
    from the sequence and all recursively contained sub-sequences
    (iterables).

    Examples:
    >>> [1, 2, [3,4], (5,6)]
    [1, 2, [3, 4], (5, 6)]
    >>> flatten([[[1,2,3], (42,None)], [4,5], [6], 7, MyVector(8,9,10)])
    [1, 2, 3, 42, None, 4, 5, 6, 7, 8, 9, 10]"""

    result = []
    for el in x:
        #if isinstance(el, (list, tuple)):
        if hasattr(el, "__iter__") and not isinstance(el, basestring):
            result.extend(flatten(el))
        else:
            result.append(el)
    return result

在你将列表压平之后，按照通常的方式执行交集操作：

c1 = [1, 6, 7, 10, 13, 28, 32, 41, 58, 63]
c2 = [[13, 17, 18, 21, 32], [7, 11, 13, 14, 28], [1, 5, 6, 8, 15, 16]]

def intersect(a, b):
     return list(set(a) & set(b))

print intersect(flatten(c1), flatten(c2))

- Geo

---

这是一段不错的压平代码，Geo。但它并没有回答问题。提问者明确期望结果以[[13,32],[7,13,28],[1,6]]的形式呈现。 - Rob Young

Answer 10

给定：

> c1 = [1, 6, 7, 10, 13, 28, 32, 41, 58, 63]

> c2 = [[13, 17, 18, 21, 32], [7, 11, 13, 14, 28], [1, 5, 6, 8, 15, 16]]

我发现以下代码可以使用集合操作，更简洁地实现相同的功能：

> c3 = [list(set(f)&set(c1)) for f in c2] 

它得到了：

> [[32, 13], [28, 13, 7], [1, 6]]

如果需要下订单：

> c3 = [sorted(list(set(f)&set(c1))) for f in c2] 

我们得到了：

> [[13, 32], [7, 13, 28], [1, 6]]

顺便说一下，如果更加偏向Python的风格的话，这种写法也可以：

> c3 = [ [i for i in set(f) if i in c1] for f in c2]

- Steven