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.

I don't think itertools gave you that error, are you using numpy? — Padraic Cunningham, Jun 18 '15 at 09:33
@user143006, how could you not be when you get an error *The truth value of an array with more than one element is ambiguous. Use a.any() or a.all()"*? — Padraic Cunningham, Jun 18 '15 at 09:42
The 2D points are retrieved through a function that appends coordinates of a np.array into 2-element lists. I can't see a connection to numpy for this exact operation though. I have created 't1/t2' as nested lists of numbers, so I guess itertools only has to deal with lists. — kalfasyan, Jun 18 '15 at 09:52

Kavin Eswaramoorthy · Accepted Answer · 2015-06-18T09:53:18.050

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

Anand S Kumar · Answer 2 · 2015-06-18T09:38:09.653

1

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.

edited Jun 18 '15 at 09:38

answered Jun 18 '15 at 09:28

Anand S Kumar

88,551
18
188
176

Because we cannot convert list to set, if the elements of the list are not `hashable`, by design, lists are not hashable, tuples are. So we need to convert the list inside the list to tuple to convert the outer list to set – Anand S Kumar Jun 18 '15 at 09:36

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

2 Answers2