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()
Comments
-
Michiyo almost 2 years
I want to find the number of common elements between two lists without eliminating duplicates.
For example:
input:
[1, 3, 3]
&[4, 3, 3]
output:
2
, since the common elements are[3, 3]
input:
[1, 2, 3]
&[4, 3, 3]
output:
1
, since the common elements are[3]
If I were to use the Kotlin collections intersect, the result is a set, which will prevent me from counting duplicate values.
I found (for Python) this, which handles duplicates differently and this, which led me to use this implementation, where
a
andb
are the lists:val aCounts = a.groupingBy { it }.eachCount() val bCounts = b.groupingBy { it }.eachCount() var intersectionCount = 0; for ((k, v) in aCounts) { intersectionCount += Math.min(v, bCounts.getOrDefault(k, 0)) }
However, being new to Kotlin I'm wondering if there's a more "Kotlin-y" way to do this--something taking advantage of all Kotlin's collections functionality? Maybe something that avoids explicitly iterating?