I searched this issue for some time but couldn't find anything relevant.
Suppose that I have two types of objects that I want to create a one-to-one correspondence between them. Let's say my first group is integers and my second group is letters. I somehow know the confidence (weight/correlation etc) of each integer, and letter pair.
Suppose also that I have 4 integers and 3 letters. Their correspondences are 1-A, 2-B, 3-C, 4-None. (I am trying to get this result)
Also, I know the relationships between ints and letters.
1 -> (A, 0.9)
2 -> (B, 0.5), (C, 0.4)
3 -> (B, 0.2), (C, 0.4)
4 -> (B, 0.1)
The rest of them are zero, for example, 2 -> (A, 0), etc.
In this example, 1-A is a pair with high confidence, 0.9, and no other integer is matching with A. So, I will add this pair to the matching pairs list. Now, I need to choose between 2-B and 2-C, vs. 3-B and 3-C. Since the former one is a better option (the sum of confidences is 0.9 as opposed to 0.6), we choose 2-B and 2-C.
After assigning 1, 2, 3, to A, B, C, respectively, 4 will be left with nothing. So, it will be none.
I can do this using some kinda brute-force algorithm but I am looking for an elegant way to do this. To me it looks like a graph algorithm but couldn't come up with something nicer than brute force.
Is there any more elegant way that I can use for this algorithm?
Language doesn't matter at this point but I am using python.
This is known as the assignment problem. This link explains one of the algorithms that can solve it, the Hungarian algorithm, and provides some C code that you should be able to copy and paste.