1

I've a problem with the nested lists. I want to compute the lenght of the intersection of two nested lists with the python language. My lists are composed as follows:

list1 = [[1,2], [2,3], [3,4]]
list2 = [[1,2], [6,7], [4,5]]
output_list = [[1,2]]

How can i compute the intersection of the two lists?

Jacopo Terrinoni
  • 173
  • 1
  • 14
  • 1
    possible duplicate of [Python - Intersection of two lists](http://stackoverflow.com/questions/642763/python-intersection-of-two-lists) – Alex Riley Apr 05 '15 at 21:37
  • i already tried that solution but it does not work for me! – Jacopo Terrinoni Apr 05 '15 at 21:41
  • Must all the elements of a sublist match all the elements of the other sublist in order to qualify as an intersection? What would be the output here? – Ambidextrous Apr 05 '15 at 21:42
  • 1
    @JacopoTerrinoni: there are solutions for lists of lists on that page, e.g. `[val for val in list1 if val in list2]`. (See [this answer](http://stackoverflow.com/a/1875493/3923281).) – Alex Riley Apr 05 '15 at 21:43
  • i can't use this method because the set() function does not work on nested lists but only on simple list – Jacopo Terrinoni Apr 05 '15 at 22:02

3 Answers3

3

I think there are two reasonable approaches to solving this issue.

If you don't have very many items in your top level lists, you can simply check if each sub-list in one of them is present in the other:

intersection = [inner_list for inner in list1 if inner_list in list2]

The in operator will test for equality, so different list objects with the same contents be found as expected. This is not very efficient however, since a list membership test has to iterate over all of the sublists. In other words, its performance is O(len(list1)*len(list2)). If your lists are long however, it may take more time than you want it to.

A more asymptotically efficient alternative approach is to convert the inner lists to tuples and turn the top level lists into sets. You don't actually need to write any loops yourself for this, as map and the set type's & operator will take care of it all for you:

intersection_set = set(map(tuple, list1)) & set(map(tuple, list2))

If you need your result to be a list of lists, you can of course, convert the set of tuples back into a list of lists:

intersection_list = list(map(list, intersection_set))
Blckknght
  • 100,903
  • 11
  • 120
  • 169
0

What about using sets in python?

>>> set1={(1,2),(2,3),(3,4)}
>>> set2={(1,2),(6,7),(4,5)}
>>> set1 & set2
set([(1, 2)])
>>> len(set1 & set2)
1
user63668
  • 101
0
import json



list1 = [[1,2], [2,3], [3,4]]
list2 = [[1,2], [6,7], [4,5]]

list1_str = map(json.dumps, list1)
list2_str = map(json.dumps, list2)

output_set_str = set(list1_str) & set(list2_str)

output_list = map(json.loads, output_set_str)

print output_list
Fomalhaut
  • 8,590
  • 8
  • 51
  • 95