Matching players in teams based on their rank

user_10244866 0
Viewed 128

I'm trying to think of a way to match n players in teams of 3 (n most likely won't exceed 30 and is a multiple of 3). The matching will be based on their ranks (the lower the number, the more skilled the player is)

The target I thought was reasonable is that to match the players in teams, such that, the maximum difference between the teams' average rank (summation of each team's rank divided by 3) is as minimum as possible (i.e the difference between the highest team in average rank and lowest team in average rank should be as minimum as possible).

I thought about trying all possible permutations but that won't be possible since the complexity would be n! (and the input could very easily exceed 20 or more)

The only feasible (yet, very naive) solution I could think of goes like this: let's say we have 12 players the need to be matched in teams. We'll sort them based on rank, then divide the sorted list into 3 parts each containing 4 players (1st 4 players are most skilled, 2nd 4 players are average skilled, 3rd 4 players are least skilled), then I'll proceed to take the first player from the first part with the last player from the last part, 2nd player from first part with (last-1) from the last part etc....

Then I'll sort those 2s based on their average rank, and will proceed to put the 1st player from the middle part (2nd part) with the team who has the highest average rank, 2nd player from 2nd part with the team with 2nd highest average rank etc.....

This is of course not an optimal solution at all. So I was wondering if there was a feasible way to go about this problem that would produce a more optimal solution?

Thank you

matching data-structures algorithm
1 Answers

A simple approach that works for your bounds

First off, we can consider a team distribution that would be clearly optimal: Every team has exactly the same sum of ranks. Unfortunately this is not always possible, as sometimes the mean power of a team will not be an integer.

The closest to this ideal we can get is to only allow teams with strength of the mean rounded up or down. For example, with 4 teams and 12 players the mean sum of ranks for a team would be 19.5, which means that ideally we'll have two teams with power 19 and two with power 20.

Given then the desired strength of all the teams, I wrote a quick script to make these teams. Specifically, it selects two players at random for a team after which we can calculate who the third player should be. If the desired third player does not yet have a team these three form a team, else we simply try again. If we are unable to form a team after several tries, we start over entirely.

Because this approach can reach any permutation randomly, and it restarts when it gets stuck, it is guaranteed to find an optimal solution if it exists.

There are two downsides: it is likely very inefficient and I have not proven the optimal solution exists. However, for less than, say, 100 players the script finds optimal solutions in reasonable time thus also proving the optimal solution exists.

Results

The results that the script generates are in this pastebin, for out-of-the-box use up to 42 teams (126 players).

The Python script itself is sufficiently poorly written, poorly optimized and generally terrible that I'm hesitant to upload it here. I expect anyone to be able to make a better version with the general idea above. However, SO requires pastebin links to be accompanied by code, so here it is:

from __future__ import division, print_function
import random
import sys

def solve(teams, players):
    playerset = set(players)
    result = None
    while True:
        result = []
        taken = set()
        for team in teams:
            for _ in range(len(teams) * 10):
                first = random.choice(players)
                while first in taken:
                    first = random.choice(players)
                second = random.choice(players)
                while second == first or second in taken or not team - first - second in playerset or team - first - second in [first, second]:
                    second = random.choice(players)
                third = team - first - second
                if third not in taken:
                    result.append(sorted([first, second, third]))
                    taken.add(first)
                    taken.add(second)
                    taken.add(third)
                    break
            else:
                break
        else:
            print_solution(result)
            return
            
def print_solution(result):
    for i, team in enumerate(result):
        print("{}: {}, {}, {}".format(i+1, *team))
    print()
    sys.stdout.flush()

def get_team_strengths(N_teams, players):
    s = sum(players)
    mean = s/N
    target = mean*3
    teams = [int(target)]*N_teams
    teams.sort()
    while sum(teams) != s:
        if sum(teams) > s:
            teams[-1] -= 1
        else:
            teams[0] += 1
        teams.sort()
    return teams

for N_teams in range(1, 43):
    N = N_teams * 3
    players = list(range(1, N+1))
    teams = get_team_strengths(N_teams, players)
    print("{} teams:".format(N_teams))
    solve(teams, players)

Again, however, I don't recommend actually using this code.

user_143177340
Related