Skip to content

hungarian ​

hungarian(costMatrix) assigns rows to distinct columns with minimum total cost. The input is an i32[][] cost matrix and the result contains the optimal cost plus row-column pairs.

SignatureReturnsComplexity
hungarian(costMatrix: i32[][])[i32, [usize, usize][]]O(n³) for an n × n matrix

For rectangular matrices, every row is assigned when enough columns exist. Negative and positive costs are supported; the returned pair list identifies the chosen column for each assigned row.

Example ​

tyrus
import { hungarian } from "tyrus:algorithm";

const result: [i32, [usize, usize][]] = hungarian([[4, 1], [2, 3]]);
print(result[0]); // 3

Study result ​

tyrus
interface HungarianInfo {
    assignments: [usize, usize][];
    totalCost: i32;
    potentialAdjustmentCount: usize;
    matrixIterationCount: usize;
}
tyrus
import { HungarianInfo, hungarianInfo } from "tyrus:algorithm";
const info: HungarianInfo = hungarianInfo([[4, 1], [2, 3]]);
print(info.assignments); // [[1, 0], [0, 1]]
print(info.totalCost); // 3
print(info.potentialAdjustmentCount); // 4
print(info.matrixIterationCount); // 2