Intersection of two lists maintaining duplicate values in Kotlin

Question

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 and b 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?

forpas · Accepted Answer · 2018-12-09T20:30:52.500

9

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

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

edited Dec 09 '18 at 20:30

answered Dec 08 '18 at 22:49

forpas

160,666
10
38
76

It can be done even shorter, without the need of a counter variable: `val result = a.intersect(b).map { x -> min(a.count {it == x}, b.count {it == x}) }.sum()` – Arjan Dec 09 '18 at 19:43
I agree it's more elegant, but the performance is the same. Anyway, do you want me to include it in the answer (of course i'll mention you). – forpas Dec 09 '18 at 19:54
Sure, you can mention it in your answer. A benefit is that it only uses values, not a variable that could be changed accidentally. And because it does not use a separate result value, it also allows us to create a oneliner function. One of the beauties of Kotlin, imo. – Arjan Dec 09 '18 at 20:07
1

This is why I consider it more elegant. – forpas Dec 09 '18 at 20:29
Interesting, thanks! It does have the downside of iterating over `a` and `b` to find counts for every element in `a.intersect(b)`. For example, if `a` and `b` hold 100000 random ints between 0 and 100000, the approach from the original question takes <200 millis and the approaches in this answer take 7-8 seconds to run. – Michiyo Dec 11 '18 at 19:40
Since the result needs all the minimum values of occurrences for each common item I can't see another way. The iteration is unavoidable. Even when sometimes this is all done under the hoods, an iteration is there. – forpas Dec 11 '18 at 19:43
Right, just a question of 1 iteration vs. multiple iterations. – Michiyo Jan 10 '19 at 17:53

score 0 · Answer 2 · answered Jan 09 '21 at 06:55

Get Common Elements from two or more arraylist

input

a = {1, 2, 2, 4, 5, 6}
b = {1, 2, 2, 4, 5, 6}
c = {1, 2, 2, 4, 6}

output = {1, 2, 2, 4, 6}

fun main() {

val array = ArrayList<ArrayList<String>>()

val arr1 = arrayListOf("1", "2", "2", "4", "5", "6")
val arr2 = arrayListOf("1", "2", "2", "4", "5", "6")
val arr3 = arrayListOf("1", "2", "2", "4", "6")

array.add(arr1)
array.add(arr2)
array.add(arr3)


println(getCommonElements(array)) }

Create a data class for storing arrayIndex and elementIndex

internal class IndexArray(val arrayIndex: Int,
                      val elementIndex: Int)

Algorithm for getting Common Elements

fun getCommonElements(arrayList: ArrayList<ArrayList<String>>): ArrayList<String> {

val commonElements = ArrayList<String>()
var isContain = true
val firstArray = arrayList[0]

val indexArray = ArrayList<IndexArray>()

// for loop for firstArray
for (e in firstArray) {

    var elementIndex: Int
    var arrayIndex: Int

    // for loop for next ArrayList
    for (i in 1 until arrayList.size) {

        if (!arrayList[i].contains(e)) {
            isContain = false
            break

        } else {
            elementIndex = arrayList[i].indexOf(e)
            arrayIndex = i

            indexArray.add(IndexArray(arrayIndex, elementIndex))
        }
    }

    if (isContain) {
        commonElements.add(e)

        // remove element
        for (i in 0 until indexArray.size) {
            arrayList[indexArray[i].arrayIndex].removeAt(indexArray[i].elementIndex)
        }

        indexArray.clear()

    } else {
        indexArray.clear()
        isContain = true
    }


}

return commonElements }

Intersection of two lists maintaining duplicate values in Kotlin

2 Answers2

Linked