matrix_match.py

from lapjv import lapjv
import numpy as np
from typing import Callable, List
def greedy_match(names1: List[str],
                 names2: List[str],
                 compare: Callable[[str, str], int],
                ) -> np.ndarray:
    result = np.zeros(len(names1), dtype=int)
    for x, sx in enumerate(names1):
        min_dist = 100
        min_y = 0
        for y, sy in enumerate(names2):
            if (dist := compare(sx, sy)) < min_dist:
                min_y = y
                min_dist = dist
        result[x] = min_y
    return result
        
def lap_match(names1: List[str],
              names2: List[str],
              compare: Callable[[str, str], int],
             ) -> np.ndarray:
    distances = np.ones(((offset := len(names1)) + len(names2),) * 2) * 100
    for y, sy in enumerate(names1):
        for x, sx in enumerate(names2):
            distances[y, offset + x] = distances[offset + x, y] = compare(sy, sx)
    row_ind, _, _ = lapjv(distances)
    assignments = row_ind[:offset] - offset
    assignments[assignments < 0] = 0
    return assignments