Issue
Example: I have the following matrix:
[
[1, 2, 4],
[5, 2, 7],
[2, 3, 3],
]
The maximum sum would be 12 (5 + 3 + 4) with the index-tuples (1, 0); (2, 1); (0, 2).
I can only think about a brute-force-solution, looping through all of the possible index-permutations calling numpy.choose with the indices and calculating the sum from the selected values. Is there a more elegant solution, maybe even a function for that in numpy or other?
Solution
This problem can be seen as an instance of the assignment problem. In assignment problem lingo the rows will be the workers, and the tasks the columns, and you need to assign one and only one worker per task minimising the overall cost.
This problem can be solved using the Hungarian Algorithm, which admits a bipartite graph formulation, therefore we can use nx.bipartite.minimum_weight_full_matching
as below:
import numpy as np
import networkx as nx
arr = np.array([[1, 2, 4],
[5, 2, 7],
[2, 3, 3], ])
flat_values = arr.flatten()
indices = [(f"r{i}", f"c{j}") for i in range(3) for j in range(3)]
G = nx.Graph()
for (start, end), length in zip(indices, flat_values):
G.add_edge(start, end, length=-1*length)
match = nx.bipartite.minimum_weight_full_matching(G, weight="length")
res = sorted((k, v) for k, v in match.items() if k.startswith("r"))
print(res)
Output
[('r0', 'c2'), ('r1', 'c0'), ('r2', 'c1')]
Here r
stands for row and c
for column
Answered By - Dani Mesejo
0 comments:
Post a Comment
Note: Only a member of this blog may post a comment.