Matching two sets: the assignment problem

A pairing picks one cell in every row and every column of the cost table

Put the costs in a table, the cost matrix: one row per red point, one column per blue point. Each cell holds the distance for that pair, rounded here to one decimal. An assignment picks one cell in each row with no two cells in the same column, so every point gets exactly one partner. Its total is the sum of the picked cells.

Taking the cheapest pair first can force an expensive pair later

A natural shortcut is greedy matching: take the cheapest pair in the table, remove its row and column, and repeat. Here it takes R2–B1 (1.0), then R3–B2 (2.0). That leaves R1 with only B3, at 6.7. The total is 9.7.

The best pairing gives up R3's cheap 2.0 and pairs R1 with B2 instead: R1–B2 (2.8), R2–B1 (1.0) and R3–B3 (2.2), a total of 6.0. Greedy fails because one cheap choice can leave a far worse one for someone else.

Subtracting a number from a whole row does not change which pairing is best

Every pairing uses exactly one cell from each row. So if you subtract 2.8 from every cell in row R1, every pairing's total drops by exactly 2.8. Their order stays the same, and so does the best one. The same holds for columns. This is the main trick of the Hungarian algorithm: subtract until zeros appear, then look for a pairing made only of zeros.

Trying every pairing stops working past about ten points

For n points there are n! pairings ("n factorial", 1 × 2 × … × n): n choices for the first red point, n − 1 for the second, and so on. The Hungarian algorithm, in its faster modern form, takes about n³ steps instead. The line-covering version in the box above is slower, about n⁴ steps at worst.

The code below checks all six pairings of the example. For real work, use a library function such as SciPy's scipy.optimize.linear_sum_assignment, which takes the cost matrix and returns the best pairing.

assign.py

import itertools
import numpy as np

cost = np.array([[4.1, 2.8, 6.7],      # row i: red point i
                 [1.0, 1.4, 5.0],      # column j: blue point j
                 [3.6, 2.0, 2.2]])
n = len(cost)
best_total, best_pairs = None, None
for pairs in itertools.permutations(range(n)):   # every way to pair them up
    total = 0.0
    for i in range(n):
        total += cost[i, pairs[i]]     # red i goes to blue pairs[i]
    if best_total is None or total < best_total:   # the first pairing, or a lower total
        best_total, best_pairs = total, pairs
print(best_pairs, round(best_total, 1))

(1, 0, 2) 6.0

itertools.permutations(range(3)) lists every ordering of 0, 1 and 2, six in all. The answer (1, 0, 2) means red 0 goes to blue 1, red 1 to blue 0, and red 2 to blue 2: R1–B2, R2–B1, R3–B3.

The two sets need not be the same size. With more blue points than red, each red point still gets one partner and some blue points get none. Library functions accept such rectangular tables.