Intersection of Lists

How to find list intersection?

If order is not important and you don't need to worry about duplicates then you can use set intersection:

>>> a = [1,2,3,4,5]
>>> b = [1,3,5,6]
>>> list(set(a) & set(b))
[1, 3, 5]

Intersection of the lists in a list (list of lists) in python

First, don't use list as a variable name - it hides the built in class.

Next, this will do it

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

The map(set,a) simply converts it to a list of sets. Then you just unpack the list and find the intersection.

If you really need the result as a list, just wrap the call with list(...)

Find elements NOT in the intersection of two lists

I usually prefer a shortcut:

set(a) ^ set(b)
{2, 4, 6}

Python - Intersection of two lists of lists

You will have to convert the lists to list of tuples, and then use the intersection. Note that below solution may have elements in a different order, and duplicates will obviously not be there, since I'm using set.

In [1]: l1 = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4], [5,9]]

In [2]: l2 = [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4], [5,6], [1,2]]

In [3]: [list(x) for x in set(tuple(x) for x in l1).intersection(set(tuple(x) for x in l2))]
Out[3]: [[1, 2], [5, 6, 2], [3], [4]]

You can alternatively save the intersection in a variable and get the final list, if order, duplicates are necessary:

In [4]: intersection = set(tuple(x) for x in l1).intersection(set(tuple(x) for x in l2))

In [5]: [x for x in l1 if tuple(x) in intersection]
Out[5]: [[1, 2], [4], [5, 6, 2], [1, 2], [3], [4]]

And the intersection, just in case if you are interested.

In [6]: print intersection
set([(1, 2), (5, 6, 2), (3,), (4,)])

This will work pretty well for large lists, but if the lists are small, do explore the other solution by @timegb (whose solution will be highly unoptimal for longer lists)

Intersect two lists and count how many times each element overlaps

Here's a simple solution using collections.Counter and set intersection. The idea is to first count occurrences of each element in each list separately; then, the number of overlaps is the min of the two counts, for each element. This matches each occurrence in one list with a single occurrence in the other, so the min gives the number of matches that can be made. We only need to count elements which occur in both lists, so we take the intersection of the two key-sets.

If you want to count all matching pairs instead (i.e. each occurrence in lst1 gets matched with every occurrence in lst2), replace min(c1[k], c2[k]) with c1[k] * c2[k]. This counts the number of ways of choosing a pair with one occurrence from lst1 and one from lst2.

from collections import Counter

def count_intersections(lst1, lst2):
    c1 = Counter(lst1)
    c2 = Counter(lst2)
    return { k: min(c1[k], c2[k]) for k in c1.keys() & c2.keys() }

Example:

>>> lst1 = ['a', 'a', 'a', 'b', 'b', 'c', 'e']
>>> lst2 = ['a', 'b', 'b', 'b', 'd', 'e']
>>> count_intersections(lst1, lst2)
{'b': 2, 'a': 1, 'e': 1}

This solution runs in O(m + n) time and uses at most O(m + n) auxiliary space, where m and n are the sizes of the two lists.

Finding intersections between two lists

I changed list2 just to show that code is working
you have some error in your code
you can do something like that:

import random

lst1 = [7, 10, 21, 35, 48, 19]
lst2 = [6,7,10]
# for i in range(10000):
#     r = random.sample(range(1, 50), 6)
#     lst2.append(r)

# HERE #(
def intersection(lst1, lst2):
   lst3 = [value for value in lst1 if value in lst2]
   return lst3  # )

def Intersection(lst1, lst2):
   return set(intersection(lst2,lst1))
print(Intersection(lst1, lst2))

Intersection of two lists including duplicates?

You can use collections.Counter for this, which will provide the lowest count found in either list for each element when you take the intersection.

from collections import Counter

c = list((Counter(a) & Counter(b)).elements())

Outputs:

[1, 1, 2, 3, 4]

Python -Intersection of multiple lists?

for 2.4, you can just define an intersection function.

def intersect(*d):
    sets = iter(map(set, d))
    result = sets.next()
    for s in sets:
        result = result.intersection(s)
    return result

---

for newer versions of python:

the intersection method takes an arbitrary amount of arguments

result = set(d[0]).intersection(*d[1:])

alternatively, you can intersect the first set with itself to avoid slicing the list and making a copy:

result = set(d[0]).intersection(*d)

I'm not really sure which would be more efficient and have a feeling that it would depend on the size of the d[0] and the size of the list unless python has an inbuilt check for it like

if s1 is s2:
    return s1

in the intersection method.

>>> d = [[1,2,3,4], [2,3,4], [3,4,5,6,7]]
>>> set(d[0]).intersection(*d)
set([3, 4])
>>> set(d[0]).intersection(*d[1:])
set([3, 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.

---

Related Topics