从两个列表的列表中寻找共同元素

Question

我有两个列表，每个列表都包含一些三维坐标，就像这样（例如）：

a = [[1, 2, 3], [4, 5, 6], [4, 2, 3]]
b[0] = [[11, 22, 3], [12, 34, 6], [41, 2, 34], [198, 213, 536], [1198, 1123, 1156]]
b[1] = [[11, 22, 3], [42, 25, 64], [43, 45, 23]]
b[2] = [[3, 532, 23], [4, 5, 6], [98, 23, 56], [918, 231, 526]]
b[n] = [[11, 22, 3], [42, 54, 36], [41, 2432, 34]]

有什么快速的方法可以查找“b”中的任何元素是否在列表“a”中具有任何坐标？例如，在给定的示例中，“a[2]”和“b [2] [1]”相同，因此我希望程序返回“true”。

- Pradeep Kumar Jha

---

你的问题是不是指的是 a[1] 和 b[2][1]？ - TerryA

是的，抱歉！我会进行编辑。 - Pradeep Kumar Jha

Answer 1

将b中最内层的列表转换为一个集合(s)，然后遍历a以检查其中是否存在任何一个元素在s中。

tot_items_b = sum(1 for x in b for y in x) #total items in b

集合提供 O(1) 的查找时间，因此总复杂度将为：

O(max(len(a), tot_items_b))

def func(a, b):
   #sets can't contain mutable items, so convert lists to tuple while storing

   s = set(tuple(y) for x in b for y in x)
   #s is set([(41, 2, 34), (98, 23, 56), (42, 25, 64),...])

   return any(tuple(item) in s for item in a)

演示：

>>> a = [[1, 2, 3], [4, 5, 6], [4, 2, 3]]
>>> b = [[[11, 22, 3], [12, 34, 6], [41, 2, 34], [198, 213, 536], [1198, 1123, 1156]], [[11, 22, 3], [42, 25, 64], [43, 45, 23]], [[3, 532, 23], [4, 5, 6], [98, 23, 56], [918, 231, 526]]]
>>> func(a,b)
True

any的帮助信息：

>>> print any.__doc__
any(iterable) -> bool

Return True if bool(x) is True for any x in the iterable.
If the iterable is empty, return False.

使用集合交集获取所有共同元素：

>>> s_b = set(tuple(y) for x in b for y in x)
>>> s_a = set(tuple(x) for x in a)
>>> s_a & s_b
set([(4, 5, 6)])

- Ashwini Chaudhary

---

这个程序能否被编辑以输出共同元素？谢谢！ - Pradeep Kumar Jha

@jhaprade 是指第一个共同元素还是所有共同元素？ - Ashwini Chaudhary

@Ashwini 如果可能的话，我想要它们全部。 - Pradeep Kumar Jha

@Bakuriu 哎呀！说得好。但是我不明白你在用什么符号？ - Ashwini Chaudhary

@AshwiniChaudhary 它应该是类似于 LaTeX 的公式（对 b 的指标求和，长度为 b 元素的总数，即 b 中所有元素的总数）。 - Bakuriu

Answer 2

使用itertools.chain.from_iterable将列表展开，然后通过简单迭代来遍历它：

>>> B = [[[11, 22, 3], [12, 34, 6], [41, 2, 34], [198, 213, 536], [1198, 1123, 1156]], [[11, 22, 3], [42, 25, 64], [43, 45, 23]], [[3, 532, 23], [4, 5, 6], [98, 23, 56], [918, 231, 526]], [[11, 22, 3], [42, 54, 36], [41, 2432, 34]]]
>>> A = [[1, 2, 3], [4, 5, 6], [4, 2, 3]]
>>> for i in itertools.chain.from_iterable(B):
...     if i in A:
...             print True, i
... 
True [4, 5, 6]

- TerryA

---

@Jared 快速展开列表的方法 - TerryA

Answer 3

使用numpy：

import numpy
b=[ [], [] , [] ]
a = [[1, 2, 3], [4, 5, 6], [4, 2, 3]]
b[0] = [[11, 22, 3], [12, 34, 6], [41, 2, 34], [198, 213, 536], 
        [1198, 1123, 1156]]
b[1] = [[11, 22, 3], [42, 25, 64], [43, 45, 23]]
b[2] = [[3, 532, 23], [4, 5, 6], [98, 23, 56], [918, 231, 526]]

for p1 in a:
    for p2 in [ p for bb in b for p in bb]:
        v=numpy.linalg.norm(numpy.array(p1)-numpy.array(p2))
        if v == 0: print p1

- perreal

Answer 4

尝试这段代码：

a = [[1, 2, 3], [4, 5, 6], [4, 2, 3]]
b={}
b[0] = [[11, 22, 3], [12, 34, 6], [41, 2, 34], [198, 213, 536], [1198, 1123, 1156]]
b[1] = [[11, 22, 3], [42, 25, 64], [43, 45, 23]]
b[2] = [[3, 532, 23], [4, 5, 6], [98, 23, 56], [918, 231, 526]]
b[3] = [[11, 22, 3], [42, 54, 36], [41, 2432, 34]]

for i in b:
    for ii in i:
        if ii in a:
            return True

它能工作，但我不确定是否快速。

- htynkn

---

使用 any 和生成器 any(ii in a for i in b for ii in i) 可以更快，但与使用集合的答案相比（除了可能非常小的输入大小），它可能仍然不够竞争力。它可能可以与 itertools.chain 解决方案竞争，但可能仍然会慢一些。 - lvc

@lvc 竞争？嘿，这不是一场竞赛。我只是提供我的答案，因为这是回答问题的另一种方式。 - TerryA

你应该将 b 初始化为一个列表：b = []，而不是字典。否则在循环 for ii in i: 中，你实际上是在尝试迭代一个整数。 - Ashwini Chaudhary