mixle.enumeration.assignment module

k-best assignment enumeration (Murty’s algorithm).

Enumerate the assignments of a cost matrix in increasing total cost – the optimal Hungarian assignment first, then the second-best, and so on – without materializing the factorial space of permutations. This is Murty’s algorithm (1968): pop the best assignment from a priority queue, then partition the remaining solution space into subproblems (each forcing some edges in and one edge out) and solve each with one Hungarian call.

The single Hungarian solve is scipy’s linear_sum_assignment; forbidden edges are marked inf (scipy avoids them and raises when a subproblem is infeasible). For an n-by-n cost matrix the optimum is O(n^3) and each of the k yielded assignments costs O(n) further Hungarian solves, so top-k is polynomial rather than O(n!).

Use k_best_assignments(cost, k) for a cost matrix directly; pass maximize=True to rank by decreasing total weight instead. MatchingDistribution consumes this to enumerate matchings in decreasing probability.

best_assignment(cost)

Return the minimum-cost assignment as (total_cost, row_ind, col_ind) (scipy Hungarian).

Parameters:

cost (ndarray)

Return type:

tuple[float, ndarray, ndarray]

k_best_assignments(cost, k=None, maximize=False)

Yield assignments of cost in increasing total cost (Murty’s algorithm).

Each item is (total_cost, row_ind, col_ind) with the original-cost total (not the internal sign-flipped one when maximize=True). Edges with non-finite cost are forbidden, so assignments that can only be completed through them are skipped. Enumeration is lazy; with k=None it runs until the (finite-cost) solution space is exhausted.

Parameters:

• cost (ndarray) – 2-D cost matrix. Rectangular is allowed (scipy matches min(n, m) edges).

• k (int | None) – maximum number of assignments to yield; None for all.

• maximize (bool) – rank by decreasing total weight instead of increasing cost (negates internally).

Yields:

(total_cost, row_ind, col_ind) in nondecreasing total cost.

Return type:

Iterator[tuple[float, ndarray, ndarray]]