Hungarian Track Assignment Cost

Problem

Find the optimal detection-to-track assignment cost.

Given an n x n cost matrix, evaluate every permutation of columns and return [minimum total cost, assignment] where assignment[i] is the column matched to row i. Break ties by keeping the lexicographically first permutation.

Hint

n is small: permutations of range(n) give the exact optimum.

Test cases

case 1

in: [[[1,2],[3,4]]]

expected: [5,[0,1]]

case 2

in: [[[1,5],[5,1]]]

expected: [2,[0,1]]

case 3

in: [[[1,2,3],[3,1,2],[2,3,1]]]

expected: [3,[0,1,2]]

case 4

in: [[[10,1],[1,10]]]

expected: [2,[1,0]]

Starter codePython

def hungarian_cost(cost):
    # Your code here
    pass

4 test cases · run your code against them in the editor