Find Intersection of Two Nested Lists

Finding the intersection of nested lists in Python?

Assuming the order does not matter, you could use set.intersection():

>>> lst = [[0, 2, 3, 4, 6], [1, 4, 5], [0, 2, 4], [4, 5]]
>>> set.intersection(*map(set,lst))
{4}
>>> set(lst[0]).intersection(*lst[1:])
{4}

Find intersection of two nested lists?

If you want:

c1 = [1, 6, 7, 10, 13, 28, 32, 41, 58, 63]
c2 = [[13, 17, 18, 21, 32], [7, 11, 13, 14, 28], [1, 5, 6, 8, 15, 16]]
c3 = [[13, 32], [7, 13, 28], [1,6]]

Then here is your solution for Python 2:

c3 = [filter(lambda x: x in c1, sublist) for sublist in c2]

In Python 3 filter returns an iterable instead of list, so you need to wrap filter calls with list():

c3 = [list(filter(lambda x: x in c1, sublist)) for sublist in c2]

Explanation:

The filter part takes each sublist's item and checks to see if it is in the source list c1.
The list comprehension is executed for each sublist in c2.

Intersection of two nested lists in Python

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

How to get intersection of each element of two nested lists in python?

[[n for n in x if n in y] for x, y in zip(a, b)]

However if the sublists are big this would be better:

[set(x).intersection(y) for x, y in zip(a, b)]

(although the order of elements is lost)

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

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

Finding intersection between two lists without duplicates in prolog

Taking advantage of the built-in sort (which also removes duplicates):

intersection_without_duplicates(Lst1, Lst2, Intersection) :-
    % Sort and remove duplicates from both
    % The built-in sort is quick
    sort(Lst1, Lst1Sorted),
    sort(Lst2, Lst2Sorted),
    intersect_sorted(Lst1Sorted, Lst2Sorted, Intersection).

intersect_sorted([], _Lst2Sorted, []).
intersect_sorted([H|T], LstSorted, Intersection) :-
    (   member_listsorted(H, LstSorted)
    ->  Intersection = [H|Intersection0]
    ;   Intersection0 = Intersection
    ),
    intersect_sorted(T, LstSorted, Intersection0).

member_listsorted(H, LstSorted) :-
    member_listsorted_(LstSorted, H).

member_listsorted_([H|T], Elem) :-
    (   H @< Elem
    ->  member_listsorted_(T, Elem)
    ;   H = Elem
    ).

Sample output in swi-prolog:

?- time(intersection_without_duplicates([a, b, c, d, b, c, d], [b, c, b, c, d],
I)).
% 31 inferences, 0.000 CPU in 0.000 seconds (89% CPU, 586277 Lips)
I = [b,c,d].

?- numlist(1, 10000, Lst1), numlist(5000, 12345, Lst2), time((intersection_without_duplicates(Lst1, Lst2, Intersection))).
% 25,060,003 inferences, 1.313 CPU in 1.297 seconds (101% CPU, 19090034 Lips)

Performance comparison with @TessellatingHeckler's suggestion:

?- numlist(1, 10000, Lst1), numlist(5000, 12345, Lst2), time((intersection(Lst1, Lst2, Both), sort(Both, Answer))).
% 35,001 inferences, 2.193 CPU in 2.167 seconds (101% CPU, 15957 Lips)

Finding common items between nested list and another list by casting them to set

Use set intersection:

s1 = set(l1)

i = s1.intersection( e[0] for e in l2 )

print(i) # set(['a', 'and', 'that', 'of', 'to', 'in', 'the'])

Set intersection (the method) can take any iterable to find the intersection with the set you call it on.

---

Your error stems from incorrectly using the lambda:

map(lambda x: set(l2[x][x]), l2[0:6]))

each x is one element of l2 (you only take the first six elements of l2. map takes each element of the input iterable and applies the function you provide. For the first element of l2 this would be:

set(l2[('the', 637)][('the', 637)]) 

wich is clearly wrong.

How to get common elements in a deep nested list: my two solutions work but take some time

You can try to convert each nested array at the second level into the set of tuples, where each lowest level array (i.e. [0,4]) is an element of the set.
The conversion into tuples is required because lists are not hashable.
Once you have each nested list of lists as a set, simply find their intersection.

set.intersection(*[set(tuple(elem) for elem in sublist) for sublist in ary])

---

Related Topics