Groovy: permutations() with size limit

Question

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?

Answer 1

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 100⁴, 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.

Answer 2

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.