Intersection of Two Lists Including Duplicates

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]

Common elements in two lists preserving duplicates

Here is my suggestion:

from collections import Counter
ac=Counter(a)
bc=Counter(b)

res=[]

for i in set(a).intersection(set(b)):
    res.extend([i] * min(bc[i], ac[i]))

>>> print(res)
[3, 5, 5]

Intersection of two lists, keeping duplicates in the first list

What do you mean you don't want to use loops? You're going to have to iterate over it one way or another. Just take in each item individually and check if it's in array2 as you go:

items = set(array2)
found = [i for i in array1 if i in items]

---

Furthermore, depending on how you are going to use the result, consider having a generator:

found = (i for i in array1 if i in array2)

so that you won't have to have the whole thing in memory all at once.

Python: intersection of 2 lists keeping duplicates from both lists

Here is the answer to your question as asked:

import collections
for A,B,expected_output in (
    ([1,1,2,3], [1,1,2,4], [1,1,1,1,2]),
    ([1,1,2,3], [1,2,4], [1,1,2])):
    cntA = collections.Counter(A)
    cntB = collections.Counter(B)
    output = [
        x for x in sorted(set(A) & set(B)) for i in range(cntA[x]*cntB[x])]
    assert output == expected_output

Here is the answer to the question as originally interpreted by myself and two others:

import collections
A=[1,1,2,3]
B=[1,1,2,4]
expected_output = [1,1,1,1,2,2]
cntA = collections.Counter(A)
cntB = collections.Counter(B)
cnt_sum = collections.Counter(A) + collections.Counter(B)
output = [x for x in sorted(set(A) & set(B)) for i in range(cnt_sum[x])]
assert output == expected_output

You can find the collections.Counter() documentation here. collections is a great module and I highly recommend giving the documentation on the whole module a read.

I realized you don't actually need to find the intersection of the sets, because the "count of a missing element is zero" according to the documentation:

import collections
for A,B,expected_output in (
    ([1,1,2,3], [1,1,2,4], [1,1,1,1,2]),
    ([1,1,2,3], [1,2,4], [1,1,2])):
    cntA = collections.Counter(A)
    cntB = collections.Counter(B)
    output = [
        x for x in sorted(set(A)) for i in range(cntA[x]*cntB[x])]
    assert output == expected_output

Intersection of two lists maintaining duplicate values in Kotlin

This:

val a = listOf(1, 2, 3, 3, 4, 5, 5, 5, 6)
val b = listOf(1, 3, 3, 3, 4, 4, 5, 6, 6, 7)

var counter = 0

a.intersect(b).forEach { x -> counter += listOf(a.count {it == x}, b.count {it == x}).min()!! }

println(counter)

will print

6

It uses the intersection of the 2 lists and by iterating through each of its items, adds to the counter the minimum number of occurrences of the item in both lists.


With this import:

import kotlin.math.min

you can avoid the creation of a list at each iteration and simplify to:

a.intersect(b).forEach { x-> counter += min(a.count {it == x}, b.count {it == x}) } 

Courtesy of Arjan, a more elegant way to calculate the sum:

val result = a.intersect(b).map { x -> min(a.count {it == x}, b.count {it == x}) }.sum()

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 two lists with duplicate elements

A possible solution to obtain the intersection D of [X|A] and B is:

• Suppose, as induction hypothesis, that the intersection of A and B is C (without repetition).
• Therefore:
  
  • if X is member of C or X is not member of B, then D is equal to C;
  • otherwise, D is equal to [X|C].

% inter(++Set1, ++Set2, -Set3)

  inter([], _, []).
  inter([X|A], B, D) :-
     inter(A, B, C),
     (   (   memberchk(X, C)
         ;   \+ memberchk(X, B) )
     ->  D = C
     ;   D = [X|C]   ).

Example:

?- inter([a,b,b,a], [c,b,b,c,e,f], S).
S = [b].

Intersection of two lists with repetitions

Map one of the sequences to a dictionary of items to the count of times they appear, then for each item in the other sequence, if it's in the collection, and the value of the lookup is greater than zero, yield it and decriment:

public static IEnumerable<T> IntersectWithRepetitons<T>(this IEnumerable<T> first,
    IEnumerable<T> second)
{
    var lookup = second.GroupBy(x => x)
        .ToDictionary(group => group.Key, group => group.Count());
    foreach (var item in first)
        if (lookup.ContainsKey(item) && lookup[item] > 0)
        {
            yield return item;
            lookup[item]--;
        }
}

This ensures that items are yields for each time they are duplicated in both sets.

You could use TryGetValue to remove a few dictionary lookups, but it sacrifices a lot of the method's elegance, so I just didn't have it in me to do that. If you care about performance, it's not a bad thing to change.

---

Related Topics