Data.Algorithm.Assignment

A solution to the assignment problem.

Documentation

assign

Arguments

:: (a -> b -> Int)

How to calculate the cost

-> [a]

The first collection

-> [b]

The second collection

-> [(a, b)]

The resulting optimal assignment (no guarantees about order)

\(\mathcal{O}(n^4)\). Assign elements from two collections to each other so that the total cost is minimal. The cost of each combination is given the by the first argument and it can be negative. If any of the collections is empty the result is the empty list. The sizes of the collections need not to match. Finally, there is no guarantees on the order of elements in the returned list of pairs.

See: https://en.wikipedia.org/wiki/Hungarian_algorithm#Matrix_interpretation