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.

Answer 1

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

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.