Algorithm to find the global minimal distance between item pairs

Question

The items a-d are to be paired with items 0-3 in such a way that the total distance between all item pairs are minimized. For example, this matrix could describe the distance between each item in the first group and an item in its counterpart group:

[[2, 2, 4, 9],
 [4, 7, 1, 1],
 [3, 3, 8, 3],
 [6, 1, 7, 8]]

This is supposed to mean that the distance 'a' -> '0' is 2, from 'a' -> '1' is 2, from 'a' -> '2' is 4, 'a' -> '3' is 9. From 'b' -> '0' it is 4 and so on.

Is there an algorithm that can match each letter with a digit, so that the total distance is minimized? E.g.:

[('a', 1), ('b', 3), ('c', 0), ('d', 2)]

Would be a legal solution with total distance: 2 + 1 + 3 + 7 = 13. Brute forcing and testing all possible combinations is not possible since the real world has groups with much more than four items in them.

Alluvium

IMHO the only way is brute-force as you descripe it. Is there a some kind of connection between the two sets? – Braca

I don't understand exactly what the rules are. Are you only allowed to pick one number out of each row and only allowed to pick one number out of each column, and you have to pick 4 numbers, and you want the sum of these 4 numbers to be minimized? – Ubiquitarian

CKoening, I would be interested to know why you dont think there's a solution. Have I stumbled upon an NP-hard problem? – Alluvium

I guess the part I don't understand is "match each letter with a digit, so that the total distance is the solution is minimized?" surely you would just match each letter to its closest digit? or are you only allowed to use each digit once? – Ubiquitarian

robert king, that is exactly right. Think of it like when you do your laundry. You want to match each of your four right socks with the most similar left sock. – Alluvium

Right.. then what yi_H said :) have fun – Ubiquitarian

Answer 1

This is a classic optimization task for bipartite graphs and can be solved with the Hungarian algorithm/method.

Haldas

Answer 2

This can be solved by treating it as an instance of a weighted bipartite matching problem. The idea is to treat the elements a-d and 0-3 as nodes in a graph, where each lettered node is connected to each numbered node with an edge whose weight is specified by the matrix. Once you have this graph, you want to find a set of edges matching letters to numbers in a way where each node is only connected to at most one edge. Such a set of edges is called a matching, and since you want to minimize the distance you are looking for a minimum-cost matching.

As yi_H points out, this problem is well-studied and has many good polynomial-time algorithms. The Hungarian Algorithm is perhaps the most famous algorithm for the problem, but others have been invented since then that are asymptotically (or practically) faster.

This problem is worth remembering, since it arises in many circumstances. Any time you need to assign items in one group to items in another, check whether you can reduce the problem to bipartite matching. If so, you've almost certainly found a fast solution to the initial problem.

Cheery