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

Question

I have two large lists of points in 2D and I want to find their common sublists, if they have some. Both of the lists are quite large and efficiency is an issue.

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

I tried itertools like below, but I get "ValueError: The truth value of an array with more than one element is ambiguous. Use a.any() or 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, but I get 'numpy.int64' object is not iterable. Also, I think this simple code would work, but it takes so much time:

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

Any advice? Thanks.

Answer 1

Lists are not hashable so we need to convert the inner list to tuple then we can use set intersection to find common element

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)

Output

set([3,41])

Since we are making the list into sets we are not accounting for repetitions. consider the following inputs

  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]]

We have two [3,41] in both the lists but the previous python program will output only one [3,41] in the output. The following program will handle duplicate entries by counting them initially and repeating them after.

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

Output

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

Answer 2

If you are really only using list then, you can create set from list and use set().intersection() for your case -

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

But with very very very large lists this method may be slow.

EDIT : Using map function.