CODEWITHSUNDEEP
algorithmsortinglanguage-agnosticranking
Charles Clayton
Charles Clayton

Reputation: 17966

What's the algorithm to assign people their most preferred value based on a list of their top choices?

Let's say users input their top three (or N) preferred baseball positions:

// first element of each list being most preferred
userA = ["backcatcher", "center field", "short stop"];
userB = ["pitcher", "backcatcher", "center field"];
userC = ["pitcher", "center field", "short stop"];
userD = ["short stop", "backcatcher", "pitcher"];
...

users = [userA, userB, userC, userD ...];

What's the algorithm to assign each user the most preferred position as possible?

I know there must be some name for this problem and the solution, but I've looked online a bunch and haven't quite found it.

It's similar to a Borda count and the Condorcet method but that takes in a users list of preferences and determines how preferred each selection is total, not by each user.

The closest I've found is the stable marriage problem, which is similar, but requires two sets of preferred lists, ie. the position "short stop" would also list which users it most wanted to play it.

Does anyone know what this problem is called? Thanks in advance.

Upvotes: 4

Views: 3492

Answers (1)

Jay Kominek
Jay Kominek

Reputation: 8783

This is the Assignment problem. You could use, for instance, the Hungarian Algorithm.

You just need to come up with a way to turn the user/player preferences into costs. Perhaps when a person gets their first choice, the cost is -3, second choice is -2, third choice is -1, etc. How you do that depends on the nature of your problem. How you view the various trade offs ends up encoded in the costs you give the algorithm.

Upvotes: 3

Related Questions