Problem is called maximum matching in bipartite graph or assignment problem. It is done by Hungarian algorithm.
On Wikipedia page are implementations in different languages. There is python library munkres with an implementation.
Frage
I want to solve a problem with Python (like a programming riddle). It isn't an exercise or anything related with this, but something I figure and I want to find a solution for it.
Problem description:
The final score of the business production will be the sum of each score in every position. I want to find the combination that will have the highest score.
A few thoughts:
So, what should be my next option? Any Python implementation ideas?
Edit: A few more details closer to Python
positionslist = [pos1, pos2, pos3, pos4, pos5, pos6, pos7, pos8, pos9, pos10]
subpositions = {"pos1":["A","B"], "pos2":["B","C"],"pos3":["A","B","C"],"pos4":["A"],"pos5":["A","B"],"pos6":["A","B","C"],"pos7":["B"],"pos8":["C"],"pos9":["A","C"],"pos10":["A"]
peoplelist = [{"pos1 A":15,"pos1 B": 8, "pos2 B": 2, "pos2 C": 4, "po3 A": 2, "pos3 B":5...}, {"pos1 A":1, "pos1 B":23,"pos2 B":11,.....},.........]
#run the code
print "best combination:" result
best combination:
pos1 B, person 3, score 23
pos2 C, person 5, score 11
pos3 A, person 18, score ..
pos4
pos5
pos6
pos7
pos8
pos9
pos10
Total Score: ....
As I said, my implementation in pseudo-code is:
for position in positionlist:
for every sub-position:
find the highest score from every person
find the highest sub-position from the previous step
remove that person from the peoplelist
store the position with the sub-position and the person
However, this is similar to Traveling Salesman Problem and it will end up with not the highest combination.
Lösung
Problem is called maximum matching in bipartite graph or assignment problem. It is done by Hungarian algorithm.
On Wikipedia page are implementations in different languages. There is python library munkres with an implementation.
Andere Tipps
If I have read this right every person has a different score for each position, and you want to find the highest score across all the combinations of people and positions - i.e. you have to calculate everyones score for each position.
I can't think of a way of expressing this that isn't the same as the Travelling salesman problem - although this is it in reverse - effectively finding the highest score combination rather than the lowest combinations.
If that is the case, then all you will be able to do reliably in a reasonable time (for any large data set) is to get a sub-optimal score which is close to and maybe exactly the optimal, but impossible to prove it is sub-optimal or optimal.
One way to try to make this simpler would be to prioritise the positions you want to fill, and get the highest score for each position in priority order - however this may not even be a close to optimal solution when compared to the non-prioritised position list.