4玩家锦标赛安排，Python

Question

我正在尝试开发一种算法来生成我的家庭每年举办的比赛的时间表。我写了一个只部分有效的解决方案；它似乎适用于2^x玩家，但不是介于两者之间。在

Parcheesi是一种一次有4个人玩的游戏，不多也不少，因此我们安排锦标赛，在第一轮有4个人（16、28、32等）的倍数，同时有n/4的游戏在玩。然后在第二轮，每个人都被洗牌和扮演新的人。在第三轮，同样的事情发生了。理想的情况下，没有人会和其他人玩两次。这是我的困境的症结所在，我试着为没有人再扮演其他人的角色编码。在

这是我这样做的方法。我确信代码中存在效率低下的地方，所以可以随意提出建议（不过，我并不担心效率）。我只想让它工作3轮以上，任何4人的倍数。在

import numpy as np
import itertools
import sys

num_players = 32
players = np.arange(1,num_players+1)

num_games = 3
games = np.arange(1,num_games+1)
game_matchups = {}

matchups = {}
for player in players:
    matchups[player] = []

for game in games:
    tables = [ [] for i in range(int(num_players/4)) ]
    for player in players:
        for i,table in enumerate(tables):
            if player in list(itertools.chain(*tables)):
                break
            if len(table) == 0:
                table.append(player)
                break
            if len(table) == 4:
                continue             
            else:
                for j,opp in enumerate(table):
                    if player in matchups[opp]:
                        break
                    else:
                        if j == len(table)-1:
                            table.append(player)
                            break
                        else:
                            continue

    game_matchups[game] = tables           
    for table in tables:
        if len(table) != 4:
            sys.exit((str(num_players)+' players with '+str(num_games)+' games doesnt work!'))
        for i,p in enumerate(table):
            matchups[p] = matchups[p] + (table[:i]+table[i+1:])
    order = order*-1

如果玩家人数是32，我最多可以安排5轮比赛。但如果我有36个球员的话，那就失败了。在第二轮比赛中，它有点“用完”了桌子，而且它不能把33号球员加到一张他还没有和别人比赛过的桌子上。在

我尝试过向后、向前/向后、交替、随机地将放入表中的玩家列表和其他人进行迭代，但似乎没有任何效果。在

在实践中，我们已经手动制定了这个时间表，并且效果良好。我想写这个程序作为对自己的一个挑战，但已经卡住了。在

Answer 1

如果你想在不重新配对的情况下进行一轮以上的比赛，你需要从16岁起将人数设为4的倍数。在

例如，如果第一张桌子上有玩家1、2、3、4（不管你如何组织其他桌子），你的第二轮至少需要4张桌子（4位玩家每人一张），以确保这4张桌子不会坐在同一张桌子上。你需要16个人来填这四张桌子。这16个人应该允许你去5个回合而不需要重新配对。鉴于1号、2号、3号和4号选手再也不能见面，他们将在剩下的几轮比赛中各自独占一张桌子。在这一点上，他们每个人都有12个对手，如果你把它完美地混合在一起，那就是每轮3人，总共4轮（总共5轮）。所以5回合是你能做的最好的16个人。在

[EDIT2]我最初认为需要16的倍数，但结果我在布景操作上犯了一个错误。你可以得到20人的多发子弹。我在两个例子中都修正了这个问题。在

下面是一个蛮力方法，它使用回溯来找到一个不会重新配对任何人的四人组合。它使用集合来控制配对冲突，itertools combinations（）函数生成四体（4的组合）和成对（4个四体中2个的组合）。在

from itertools import combinations,chain

def arrangeTables(players, tables, alreadyPaired):
    result        = [[]] * tables # list of foursomes
    tableNumber   = 0
    allPlayers    = set(range(1,players+1))
    foursomes     = [combinations(allPlayers,4)]
    while True:
        foursome = next(foursomes[tableNumber],None)
        if not foursome:
            tableNumber -= 1
            foursomes.pop()
            if tableNumber < 0: return None
            continue
        foursome = sorted(foursome)
        pairs    = set(combinations(foursome,2))
        if not pairs.isdisjoint(alreadyPaired): continue
        result[tableNumber] = foursome
        tableNumber += 1
        if tableNumber == tables: break
        remainingPlayers = allPlayers - set(chain(*result[:tableNumber]))
        foursomes.append(combinations(remainingPlayers,4))
    return result

def tournamentTables(players, tables=None):
    tables  = tables or players//4
    rounds  = []    # list of foursome for each round (one foresome per table)
    paired  = set() # player-player tuples (lowest payer number first)
    while True:
        roundTables = arrangeTables(players,tables,paired)
        if not roundTables: break
        rounds.append(roundTables)
        for foursome in roundTables:
            pairs = combinations(foursome,2)
            paired.update(pairs)
    return rounds

这将产生以下结果：

^{pr2}$

如果你想做的回合数超过了人数所允许的数量，你可以调整它来使用Counter（）（from collections）而不是集合来实现每个玩家的“最大重新配对计数”。在

[编辑]以下是函数的一个变体，具有最大的配对参数和玩家分布的随机性：

^{3}$

这个版本将让你决定你愿意接受多少对每个玩家达到更高的回合数。在

for roundNumber,roundTables in enumerate(tournamentTables(12,2)):
    print(roundNumber+1,roundTables)

1 [[3, 6, 8, 10], [1, 2, 5, 7], [4, 9, 11, 12]]
2 [[1, 4, 5, 11], [3, 6, 7, 8], [2, 9, 10, 12]]
3 [[1, 4, 8, 9], [5, 6, 7, 12], [2, 3, 10, 11]]

请注意，您仍然可以使用最多1个以不允许重新配对（即每个玩家组合1个配对）：

for roundNumber,roundTables in enumerate(tournamentTables(20)):
    print(roundNumber+1,roundTables)

1 [[1, 2, 3, 4], [13, 14, 15, 16], [17, 18, 19, 20], [9, 10, 11, 12], [5, 6, 7, 8]]
2 [[3, 7, 14, 18], [4, 11, 15, 19], [1, 5, 9, 13], [2, 6, 10, 17], [8, 12, 16, 20]]
3 [[2, 5, 12, 18], [1, 6, 11, 14], [4, 9, 16, 17], [3, 8, 13, 19], [7, 10, 15, 20]]

[EDIT3]优化版本。在

我对这个函数进行了更多的实验，并添加了一些优化。它现在可以在合理的时间内完成36人组合。正如我所怀疑的那样，大部分时间都花在试图（并且失败）找到第六轮解决方案上。这意味着，如果你一有5发子弹就退出这个功能，你总能得到快速的反应。在

更进一步，我发现，超过32人，一些球员计数需要更长的时间。他们浪费了额外的时间来确定在找到可能的回合后没有更多可能的回合（例如，36人5回合）。所以36，40和44个玩家需要更长的时间，但是48个玩家更快地收敛到5轮解。数学家可能对这种现象有一个解释，但在这一点上我无法解释。在

现在，我发现当你有64个人或更多人时，这个函数只会产生5发以上的子弹。（所以在5点停止似乎是合理的）

以下是优化功能：

def arrangeTables(players, tables, alreadyPaired):
    result        = [[]] * tables # list of foursomes
    tableNumber   = 0
    threesomes    = [combinations(range(2,players+1),3)] 
    firstPlayer   = 1     # first player at table (needs 3 opponents)
    placed        = set() # players sitting at tables so far (in result)
    while True:
        opponents = next(threesomes[tableNumber],None)
        if not opponents:
            tableNumber -= 1
            threesomes.pop()
            if tableNumber < 0: return None
            placed.difference_update(result[tableNumber])
            firstPlayer = result[tableNumber][0] 
            continue
        foursome    = [firstPlayer] + list(opponents)
        pairs       = combinations(foursome,2)
        if not alreadyPaired.isdisjoint(pairs): continue
        result[tableNumber] = foursome
        placed.update(foursome)
        tableNumber += 1
        if tableNumber == tables: break
        remainingPlayers = [ p for p in range(1,players+1) if p not in placed ]
        firstPlayer = remainingPlayers[0]
        remainingPlayers = [ p for p in remainingPlayers[1:] if (firstPlayer,p) not in alreadyPaired ]
        threesomes.append(combinations(remainingPlayers,3))       
    return result

def tournamentTables(players):
    tables  = players//4
    rounds  = []    # list of foursome for each round (one foresome per table)
    paired  = set() # player-player tuples (lowest payer number first)
    while True: # len(rounds) < 5
        roundTables = arrangeTables(players,tables,paired)
        if not roundTables: break
        rounds.append(roundTables)
        for foursome in roundTables:
            paired.update(combinations(foursome,2))
    return rounds

优化是基于这样一个事实：对于每个新表，第一个玩家可以是剩余的任何一个。如果一个有效的玩家组合存在，我们会在第一个位置找到它。没有必要在该位置验证与其他玩家的组合，因为这些组合只是剩余表/玩家的排列，这些表/玩家将被第一个位置的玩家覆盖。在

这允许逻辑处理3的组合，而不是剩余玩家列表中的4的组合。它还允许通过只合并没有与占据第一位置的玩家配对的对手，来早期筛选出剩余的玩家。在