1
\$\begingroup\$

I have a problem to solve. My algorithm is assigning Players to Positions. On the start I have a list of about 16 positions and 4 players. The problem is to assing every player to it's closest positions so the overall distance is as low as possible.

I've already done this:

List players = ...
List positions = ...
Set posPerms = positions.permutations().collect { it.subList(0, playmakers.size()) } as Set
List assignation = posPerms.min { List perm ->
    int v = 0
    perm.eachWithIndex { Position pos, int index ->
        v += pos.distance(players[index])
    }
    v
}
[players, assignation].transpose().collectEntries { it }

I get what I want, but the performance is a problem. positions.permutations() generates massive lists. Is there any more optimal way to do this?

\$\endgroup\$

migrated from stackoverflow.com Mar 5 '12 at 19:29

This question came from our site for professional and enthusiast programmers.

2
\$\begingroup\$

If you have always at most 4 player and the number of positions is smaller than 100 (like your 16 start positions), then checking all possible position and players takes 1004, which is small enough. but if you looking for faster solution (harder implementation) You can use Maximum Weighted Matching by Edmound, First you should create a graph, you can draw graph, by setting

Vertices = players position Union available position as nodes.
Edges = draw edge between each player and all available positions

For setting weight to edges you should do it in reverse, In fact first find the maximum distance (between all possible (player , position) pair, name it MaxDistance, now set your graph edges as MaxDistance - EdgeDistance + 1, here EdgeDistance is distance between player and desired position.

You can find good implementation of Edmond's algorithm in c++ in Lemon package.

\$\endgroup\$
0
\$\begingroup\$

You could use the eachPermutation method to avoid building the set of permutations in memory.

That said, with 16 positions there will be about 2 billion permutations. You might want to think about a more efficient algorithm. I think this problem is an instance of the Assignment problem. The Hungarian algorithm can solve this using a matrix of values of size players * positions, instead of the factorial of positions.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.