从 N 名玩家中生成每场可能的比赛，并创建 N-1 组，每组 N/2 场比赛

Question

我正在尝试编写一个脚本，生成来自 N 玩家的所有可能的 1v1 比赛，然后创建 N-1 组（天）的 N/2 玩家，以便每天每个人都玩，到所有 N-1 天结束时，每个玩家都将与所有其他玩家对战。

就我而言：

N = 12 名玩家
N-1 = 11 天
N/2 = 每天 6 场比赛
Number of matches = formula

我写了下面的脚本，但效果不是很好。我使用 player_combinations() 生成每个可能的匹配项。然后，我重复 N-1 次以创建 N-1 组（天）。我确保每天只包含一个给定的玩家一次，在继续第二天之前，我从 combinations 中减去 day 并清除 day，这样我就不会使用相同的匹配项两次。

问题是，在运行脚本之后，并非每个组都有相同数量的参与者，并且匹配的总数加起来不正确（较低）。

我该怎么办？有没有一种简单的方法（可能使用分区、排列等）来解决我没有看到的这个问题？

脚本：

from itertools import combinations


def player_combinations(players):
    return [' - '.join(i) for i in combinations(players, 2)]


p = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L']

combinations = player_combinations(p)
day = []

for i in range(len(p)-1):
    for pair in combinations:
        if not any(pair.split(' - ')[0] in participants for participants in day) and not any(pair.split(' - ')[1] in participants for participants in day):
            day.append(pair)

    for participants in day:
        print(participants)
    print()

    for participants in day:
        if participants in combinations:
            combinations.remove(participants)

    day.clear()

Answer 1

此处回答：https://math.stackexchange.com/questions/1477767/efficiently-partition-a-set-into-all-possible-unique-pair-combinations

这个想法是在N个顶点上做一个完整的图，把除了一个顶点之外的所有顶点都放在一个正多边形上，一个在中心。然后我们进行边缘着色 s.t。每个顶点恰好与每个边颜色关联一次。然后颜色代表锦标赛的轮次，每个彩色边代表该轮中的一对端点。

我们将包含中心顶点的边称为“中心边”。我们通过以下方式形成着色：

首先对中央边缘使用所有颜色（圆形）。
然后，用给定中心边缘的颜色为垂直于给定中心边缘的所有边缘着色。

例如，标记为 0-11 的 12 个顶点，标记为 0-10 的 11 个圆，'colors'。

将顶点 11 视为中心顶点。
用颜色 i 给从 11 到 i 的边着色。
使用颜色 i 进行配对/颜色边 (mod(i-j,11),mod(i+j,11))，对于 {1,2,3,4 中的 j ,5}.

回合配对：

(11,0), (10,1), (9,2), (8,3), (7,4), (6,5)
(11,1), (0,2), (10,3), (9,4), (8,5), (7,6)
(11,2), (1,3), (0,4), (10,5), (9,6), (8,7)
(11,3), (2,4), (1,5), (0,6), (10,7), (9,8)
(11,4), (3,5), (2,6), (1,7), (0,8), (10,9)
(11,5), (4,6), (3,7), (2,8), (1,9), (0,10)
(11,6), (5,7), (4,8), (3,9), (2,10), (1,0)
(11,7), (6,8), (5,9), (4,10), (3,0), (2,1)
(11,8), (7,9), (6,10), (5,0), (4,1), (3,2)
(11,9), (8,10), (7,0), (6,1), (5,2), (4,3)
(11,10), (9,0), (8,1), (7,2), (6,3), (5,4)

Answer 2

我已经使用下面的参考资料为您的示例制作了循环类型脚本。这将以一种特殊的方式对每个玩家进行配对，以确保每轮中所有或几乎所有（在奇数玩家的情况下）玩家的回合数最少

此处参考：https://nrich.maths.org/1443

import math

def shuffle(players): # rotate the values in players so the last player is first and everyone else is shifted one down
    shuffled = list(players[-1])
    shuffled.extend(players[:-1])
    return shuffled

def pair_up_players(players, shuffled_players): # pair up the values in players, round robin style
    pairs = []
    idx_left_side_players = range(math.floor(len(shuffled_players)/2))
    for idx in idx_left_side_players:
        p1 = shuffled_players[idx]
        p2 = shuffled_players[-idx-1-len(shuffled_players)%2]
        pairs.append((p1, p2))

    # if even number of players, pair up the last shuffled player with the last player in players
    if len(players) % 2 == 0:
        p1 = shuffled_players[-1]
        p2 = players[-1]
        pairs.append((p1, p2))

    return pairs


players = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L']
num_players = len(players)
rounds_to_play = num_players - 1 + num_players%2
result = []

# we shuffle all or all but the last player depending if num_players is even or odd
if num_players % 2 == 0: # even, shuffle all players except for the last one, which is static
    shuffled_players = players[:-1]
else:
    shuffled_players = players # shuffle all players around

# loop the rounds
for round in range(rounds_to_play):
    print(shuffled_players)
    result.append(pair_up_players(players, shuffled_players))
    shuffled_players = shuffle(shuffled_players)

print(result)

从 N 名玩家中生成每场可能的比赛，并创建 N-1 组，每组 N/2 场比赛

Generate each possible match from N players and create N-1 groups of N/2 matches each

python

algorithm

combinatorics