Python - 两个列表中嵌套列表的交集

Question

这是我的两个列表：

k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4], [5,9]]
kDash = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4], [5,6], [1,2]]

我的输出应该是以下内容：

[[1, 2], [4], [5, 6, 2], [1, 2], [3], [4]]

我该如何得到这个输出结果呢？

提前感谢你的帮助。

- Nimmi Rashinika

---

我发现的问题是无法将一个列表的列表转换为集合，如果可能的话，这个交集可以很容易地被取出。 - Nimmi Rashinika

请解释获得输出的逻辑。 - timgeb

你能解释一下为什么 [5, 6] 和 [5, 9] 在交集中吗？ - NiziL

对不起，那是我的错误，我会纠正它。 - Nimmi Rashinika

Answer 1

您需要将列表转换为元组列表，然后使用交集。请注意，下面的解决方案可能会有不同顺序的元素，并且显然不会有重复项，因为我使用了set。

In [1]: l1 = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4], [5,9]]

In [2]: l2 = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4], [5,6], [1,2]]

In [3]: [list(x) for x in set(tuple(x) for x in l1).intersection(set(tuple(x) for x in l2))]
Out[3]: [[1, 2], [5, 6, 2], [3], [4]]

你可以选择将交集保存在一个变量中，并获取最终的列表，如果需要保留顺序和重复项：

In [4]: intersection = set(tuple(x) for x in l1).intersection(set(tuple(x) for x in l2))

In [5]: [x for x in l1 if tuple(x) in intersection]
Out[5]: [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4]]

如果您感兴趣的话，这是交集。

In [6]: print intersection
set([(1, 2), (5, 6, 2), (3,), (4,)])

这种方法在处理大型列表时效果良好，但如果列表很小，则请尝试@timegb提供的其他解决方案（该解决方案对于较长的列表来说将非常不优化）。

- Anshul Goyal

Answer 2

由于你的输出列表具有重复元素，你似乎并不需要经典的交集。一个基本的列表推导式将完成所有工作。

>>> k = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4], [5,9]]
>>> kDash = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4], [5,6], [1,2]]
>>> [x for x in k if x in kDash]
[[1, 2], [4], [5, 6, 2], [1, 2], [3], [4]]

对于大型列表，我们希望将调用__contains__的时间从O(n)降为O(1):

>>> stuff_in_kDash = set(map(tuple, kDash))
>>> [x for x in k if tuple(x) in stuff_in_kDash]
[[1, 2], [4], [5, 6, 2], [1, 2], [3], [4]]

- timgeb

---

如果你需要删除重复元素，可以看看这个答案 ;) - NiziL

这种方法的速度比set交集方法慢得多。其缩放程度大约为O(n²k)，其中n是子列表的数量，k是每个子列表的平均长度。 - Veedrac

我刚刚意识到OP的输出列表中有重复元素。所以，除非规格发生变化，否则列表生成式是解决问题的方法。 - timgeb

我认为你的优化版本可能在每次循环中重新创建了set进行测试，所以它实际上没有解决 O(n) 问题... - ShadowRanger

@ShadowRanger 真是太对了，我刚刚用 set 的子类进行了测试，当调用 __init__ 时会打印一些内容。我会编辑我的回答。 - timgeb

Answer 3

更简洁的方式是这样写交集：

{tuple(x) for x in l1} & {tuple(x) for x in l2}

一个不错的选择是：

{tuple(x) for x in l1}.intersection(map(tuple, l2))

- Veedrac

Answer 4

尽管这里所写的更为优雅，但这是另一种解决方案

def foo(L1,L2):
    res=[]
    for lst in L1:
        if lst in L2:
            res.append(lst)
    return res

- limitless