2

A lot of posts or How to find list intersection? aim to find to unique items between two lists:

Here are my two lists:

list1=[1, 2, 2, 3, 3, 4, 4, 5, 10, 12] 
list2=[1, 1, 2, 2, 3, 4, 4, 5, 8, 18]

my answer is to find common items, the items can be repeated. for example, one 1 appears in those two lists, therefore, res should contain one 1. Two 2 appear in the two lists, res should contain two 2, etc.

res = [1 ,2, 2, 3, 4, 4, 5]

The order does not matter, my attempt is to use:

res = [x for x in list2 if x in list1]
# res = [1, 1, 2, 2, 3, 4, 4, 5] by above code

However, it is not correct, so how can I do that?

RonnieChen
  • 103
  • 4
jason
  • 1,998
  • 3
  • 22
  • 42
  • 2
    Possible duplicate of [How to find list intersection?](https://stackoverflow.com/questions/3697432/how-to-find-list-intersection) – DYZ Sep 09 '19 at 03:23
  • Actually, my result list can contain repeat items. – jason Sep 09 '19 at 03:24
  • There is a suitable answer to your question on that page. – DYZ Sep 09 '19 at 03:25
  • @DYZ there isn't... All answers for that question remove duplicate intersections, hence the emphasis on `unique` in jason's question. – Lord Elrond Sep 09 '19 at 06:27

3 Answers3

1

The only way I could think to do this is by removing items from list2 as you go:

list1 = [1, 2, 2, 3, 3, 4, 4, 5, 10, 12]
list2 = [1, 1, 2, 2, 3, 4, 4, 5, 8, 18]

res = []

for x in list1:
    if x in list2:
        res.append(x)
        list2.remove(x)

print(res)

I'm curious if there are better answers out there.

Lord Elrond
  • 13,430
  • 7
  • 40
  • 80
0

The traditional approach won't work since inside the second for loop it iterates the entire list again and finds the same element again even though it was considered earlier.

You need a mechanism to eliminate the element which is already considered.
Eg: When you iterate list1 over list2 and come across 3. In the first iteration, you'll find it in the list2. But, as you move forward and consider the next element which is again 3, you'll again find it as a common element in list2 since you are iterating the list2 from the beginning.

Here's a solution:

Once we come across a duplicate element in list2, we remove it from list2.


a = [1, 2, 2, 3, 3, 4, 4, 5, 10, 12]
b = [1, 1, 2, 2, 3, 4, 4, 5, 8, 18]

def remove_duplicates(x,y):
    res = []
    for i in x:
        for j in y:
            if j == i:
                res.append(j)
                y.remove(j)
    return res
    
print(remove_duplicates(a,b))

Another approach using functional programming would be to covert the list2 into a data structure using map() such that it holds two values for each element in the list: [(1, True),(2, True), ...]

While iterating, only visit elements who are set to True
And, whenever we find a common element, we set that element's True to False

Community
  • 1
  • 1
saintlyzero
  • 1,632
  • 2
  • 18
  • 26
0

An alternative solution based on Counter:

import collections

def intersection(A,B):
    c_a=collections.Counter(A)
    c_b=collections.Counter(B)
    duplicates=[]
    for c in c_a:
        duplicates+=[c]*min(c_a[c],c_b[c])
    return duplicates


list1=[1, 2, 2, 3, 3, 4, 4, 5, 10, 12] 
list2=[1, 1, 2, 2, 3, 4, 4, 5, 8, 18]
print(intersection(list1,list2))
catbow
  • 85
  • 9