两个列表列表之间的公共元素（嵌套列表的交集）

Question

我有两个大的二维点列表，如果有的话，我想找到它们的公共子列表。两个列表都比较大，效率是个问题

t1 = [[3, 41], [5, 82], [10, 31], [11, 34], [14, 54]]
t2 = [[161, 160], [169, 260], [187, 540], [192, 10], [205, 23]]

我尝试了如下所示的 itertools，但我得到“ValueError：具有多个元素的数组的真值不明确。使用 a.any() 或 a.all ()".

for i in itertools.chain.from_iterable(t1):
    if i in t2:
        print "yes",i

I tried the first answer from here too，但我得到 'numpy.int64' object is not iterable. 另外，我认为这个简单的代码可以工作，但它需要很多时间：

intersection = [i for i in t1 if i in t2]

有什么建议吗？谢谢

Answer 1

如果您真的只使用 list 那么，您可以从列表中创建 set 并使用 set().intersection() 来满足您的需求 -

l1 = [[1,2],[2,3]]
l2 = [[3,4],[2,3]]
list(set(map(tuple,l1)).intersection(set(map(tuple,l2))))
>> [(2, 3)]

但是对于非常非常非常大的 lists 这种方法可能会很慢。

编辑：使用map函数。

Answer 2

列表不可散列，因此我们需要将内部列表转换为元组，然后我们可以使用集合交集来查找公共元素

t1 = [[3, 41], [5, 82], [10, 31], [11, 34], [14, 54]]
t2 = [[161, 160], [169, 260], [187, 540], [192, 10], [205, 23], [3,41]]

nt1 = map(tuple, t1)
nt2 = map(tuple, t2)

st1 = set(nt1)
st2 = set(nt2)

print st1.intersection(st2)

输出

set([3,41])

由于我们将列表分成集合，因此我们不考虑重复项。考虑以下输入

  t1 = [[3, 41], [3, 41], [5, 82], [10, 31], [11, 34], [14, 54]]
  t2 = [[3,41], [3,41], [161, 160], [169, 260], [187, 540], [192, 10], [205, 23]]

我们在两个列表中都有两个 [3,41]，但之前的 python 程序将在输出中仅输出一个 [3,41]。以下程序将通过最初计算重复条目并在之后重复它们来处理重复条目。

t1 = [[3, 41], [3, 41], [5, 82], [10, 31], [11, 34], [14, 54]]
t2 = [[3,41], [3,41], [161, 160], [169, 260], [187, 540], [192, 10], [205, 23]]

nt1 = map(tuple, t1)
nt2 = map(tuple, t2)

st1 = set(nt1)
st2 = set(nt2)

from collections import defaultdict
d1 = defaultdict(int)
d2 = defaultdict(int)
for i in nt1:
    d1[i] += 1#counting element occurrence from first list

for i in nt2:
    d2[i] += 1 #counting element occurrence from second list

result_list = []

for i in st1.intersection(st2):
    min_count = min(d1[i], d2[i]) #selecting the minimum one to multiply
    result_list+=map(lambda x:list(i), xrange(0, min_count))

print result_list

输出

[[3, 41], [3, 41]]

两个列表列表之间的公共元素（嵌套列表的交集）

Common elements between two lists of lists (intersection of nested lists)

python

numpy

nested-lists

python-2.7