CODEWITHSUNDEEP
arraysalgorithmkotlinstring-matching
Gurwinder Singh
Gurwinder Singh

Reputation: 39507

Find best match for each word without double matching

I have two string arrays and I want to match each string of first array with each of second and show average score.

Naive implementation in Kotlin would be:

fun main(args: Array<String>) {
    val jw = JaroWinklerDistance()
    val a = arrayOf("FRITZ", "FRUITS")
    val b = arrayOf("FRITZ", "MARTIN", "FOOBAR")

    var score = 0.0
    a.forEach { x ->
        var current = 0.0
        b.forEach { y ->
            current = max(current, jw.apply(x, y))
        }
        score += current
    }
    score /= a.size

    println("Average score $score")
}

It prints:

Average score 0.9288888888888889

But this is not what I need. The word FRITZ is already exactly matched in both the arrays. So it should match the remaining FRUITS with MARTIN and FOOBAR. So average score should be calculated as:

FRITZ  - FRITZ  : 1
FRUITS - MARTIN : 0.5555555555555555
FRUITS - FOOBAR : 0.4444444444444444

FRITZ  = 1
FRUITS = max (0.5555555555555555, 0.4444444444444444)
       = 0.5555555555555555

Average score = (1 + 0.5555555555555555) / 2
              = 0.7777777777777778

Does this problem resembles any existing problems? I am just looking for the algorithm, not code.

I have tried different approaches without luck. Could anyone please help?

Upvotes: 0

Views: 58

Answers (1)

btilly
btilly

Reputation: 46445

The problem is to find an optimal matching. This is called the Assignment Problem

Upvotes: 1

Related Questions