根据排名匹配团队中的球员

Question

我正在想办法匹配 3 人一组的 n 个玩家（n 很可能不会超过 30，并且是 3 的倍数）。匹配将根据他们的排名（数字越小，玩家的水平越高）

我认为比较合理的目标是匹配球队中的球员，使得球队平均排名（每支球队排名之和除以3）之间的最大差异尽可能小（即平均排名最高的球队和平均排名最低的球队之间的差距应该尽可能小）。

我考虑过尝试所有可能的排列，但这是不可能的，因为复杂度为 n！（并且输入很容易超过 20 个或更多）

我能想到的唯一可行（但非常幼稚）的解决方案是这样的：假设我们有 12 名球员需要在团队中匹配。我们将根据排名对他们进行排序，然后将排序后的列表分成 3 部分，每部分包含 4 名玩家（第 4 名玩家技能最高，第二 4 名玩家技能一般，第三 4 名玩家技能最低），然后我将继续将第一部分的第一个玩家与最后一部分的最后一个玩家、第一部分的第二个玩家与最后一部分的 (last-1) 等....

然后我将根据他们的平均排名对这些 2 进行排序，然后将中间部分（第 2 部分）的第 1 名球员与平均排名最高的球队放在一起，第 2 部分的第 2 名球员与平均排名第二的球队等......

这当然不是最佳解决方案。所以我想知道是否有可行的方法来解决这个问题，从而产生更优的解决方案？

谢谢

Answer 1

适合您的界限的简单方法

首先，我们可以考虑一个明显最优的团队分布：每个团队的排名总和完全相同。不幸的是，这并不总是可能的，因为有时团队的平均力量不是整数。

我们能得到的最接近这个理想的是只允许球队的平均实力向上或向下舍入。例如，有 4 支球队和 12 名球员，一支球队的平均排名总和为 19.5，这意味着理想情况下我们将拥有两支力量为 19 的球队和两支力量为 20 的球队。

考虑到所有团队的预期实力，我写了一个快速脚本来制作这些团队。具体来说，它会为一个团队随机选择两名球员，然后我们可以计算出第三名球员应该是谁。如果想要的第三个玩家还没有团队，这三个人组成一个团队，否则我们再试一次。如果多次尝试仍无法组队，则完全重新开始。

因为这种方法可以随机到达任意排列，遇到卡住就重新开始，所以保证找到最优解（如果存在）。

有两个缺点：它可能效率很低，而且我还没有证明存在最佳解决方案。然而，对于少于 100 名玩家，脚本会在合理的时间内找到最优解，从而也证明存在最优解。

结果

脚本生成的结果是 in this pastebin，开箱即用，最多 42 个团队（126 名玩家）。

Python 脚本本身写得很糟糕，优化很差，而且通常很糟糕，我犹豫要不要把它上传到这里。我希望任何人都能根据上面的总体思路做出更好的版本。但是，SO 要求 pastebin 链接附有代码，所以这里是：

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)

不过，我还是不建议实际使用此代码。

根据排名匹配团队中的球员

Matching players in teams based on their rank

algorithm

matching

data-structures

适合您的界限的简单方法

结果