Find the combination of variables in base of their score

Question

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:

• Let's say that I have a business with 10 different working positions.
• Each position has a few different sub-positions. For example (aggressive, relaxed, normal). But, the sub-positions do not be the same for every position. Other have 1, other have 2, other 3.
• I have 20 people with their performance-score in every position and sub-position.

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:

• Not all the people will get the job, since the positions are less than the number of people.
• I cannot have two people in the same position.
• My first attempt was to take the highest score of each people and trying to fill all the positions one by one. But this ended up with a problem. A problem similar to the traveling salesman.

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.

Answer 1

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.