Home > Back-end >  Return only elements with maximum number of ocurrences
Return only elements with maximum number of ocurrences

Time:12-04

Lets say we have the following structure in Kotlin for example:

val allExams = setOf("A", "B", "C", "D", "E", "F")
val examMap = mutableMapOf<String, Set<String>>()
examMap["1"] = setOf("A","B")
examMap["2"] = setOf("A","B","C")
examMap["3"] = setOf("A","B","C","D")
examMap["4"] = setOf("E")
examMap["5"] = setOf("F")

How can I filter to only maintain in map items with the maximum number of matched elements?

In the said example i want to remove examMap["1"] and examMap["2"] because in examMap["3"] i have "A", "B", "C" and "D" (which is the item with maximum number of matching elements from allExams). The examMap["4"] and examMap["5"] are to be maintained because are the only items on the map that has these values.

So in the end I want to have the map with the following values:

examMap["3"] = setOf("A","B","C","D")
examMap["4"] = setOf("E")
examMap["5"] = setOf("F")

CodePudding user response:

This will give you the expected result:

val result = mutableMapOf<String, Set<String>>()
examMap.toList().sortedByDescending { (_, v) -> v.size }
    .forEach {
        if (result.isEmpty() 
            || result.values.none { rList -> rList.containsAll(it.second) }) {
            result.put(it.first, it.second)
        }
    }
}

The Idea is:

  • first sort the Sets in the map by the set.size descending.Because, the more elements in the set, the better chance it has to cover other sets
  • then start from the largest set, check if already picked sets (in result) have contained all the elements in the current set, to decide if append it to the result

With the given input, the result will be:

{3=[A, B, C, D], 4=[E], 5=[F]}
  • Related