1

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

Parcheesi 是一次有 4 人参加的游戏，不多也不少，因此我们安排比赛时有 4 人的倍数（16、28、32 等）。在第 1 轮中，有 n/ 4场比赛同时进行。然后在第 2 轮中，每个人都洗牌并扮演新人。在第 3 轮中，同样的事情发生了。理想情况下，没有人会两次扮演任何其他人。这就是我的困境的症结所在，试图编码没有人再扮演其他人的属性。

这是我这样做的方法。我确定代码效率低下，因此请随时提出建议（不过，我并不担心效率）。我只希望它适用于 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 名玩家，它就会中断。它在第 2 轮中有点“用完”牌桌，并且无法将玩家 33 添加到他还没有玩过某人的牌桌。

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

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

4

1 回答 1

1

如果您想在不重新配对的情况下进行多轮比赛，您将需要从 16 岁开始的人数为 4 的倍数。

例如，如果您在第一张桌子上有玩家 1、2、3、4（无论您如何组织其他桌子），那么您的第二轮将需要至少 4 张桌子（4 名玩家每人一张）以确保这四个人不坐在同一张桌子上。你需要 16 个人来填满这四张桌子。这 16 个人应该可以让你在不重新配对的情况下进行 5 轮比赛。鉴于玩家 1、2、3 和 4 永远无法再次相遇，他们将在剩余的回合中各自独占一张桌子。到那时，他们每人还有 12 人要对抗，如果你完美地混合，那就是每轮 3 人，总共 4 轮（总共 5 轮）。所以 5 轮是 16 人能做的最好的。

[EDIT2] 我最初认为需要 16 的倍数，但事实证明我在集合操作中犯了一个错误。您可以为 20 人获得多轮。我在两个示例中都修复了它。

以下是一种蛮力方法，它使用回溯来找到不会重新配对任何人的四人组合。它使用集合来控制配对碰撞和 itertools combination() 函数来生成四人组（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

这将产生以下结果：

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

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

如果您想进行比人数允许的更多的回合，您可能需要调整它以使用 Counter()（来自集合）而不是集合来实现每个玩家的“最大重新配对计数”。

[编辑] 这是具有最大配对参数和玩家分布随机化的函数的变体：

from itertools import combinations,chain
from collections import Counter
from random import shuffle

def arrangeTables(players, maxPair, alreadyPaired):
    tables        = players//4
    result        = [[]] * tables # list of foursomes
    tableNumber   = 0
    allPlayers    = set(range(1,players+1))

    def randomFoursomes():
        remainingPlayers = list(allPlayers - set(chain(*result[:tableNumber])))
        if maxPair > 1: shuffle(remainingPlayers)
        return combinations(remainingPlayers,4)

    foursomes     = [randomFoursomes()]
    allowedPairs  = 1
    while True:
        foursome = next(foursomes[tableNumber],None)
        if not foursome and allowedPairs < maxPair:
            foursomes[tableNumber] = randomFoursomes()
            allowedPairs += 1
            continue
        if not foursome:            
            tableNumber -= 1
            if tableNumber < 0: return None
            allowedPairs = 1
            foursomes.pop()
            continue
        foursome = sorted(foursome)
        if any(alreadyPaired[pair] >= allowedPairs for pair in combinations(foursome,2)):
            continue
        result[tableNumber] = foursome
        tableNumber   += 1
        if tableNumber == tables: break
        foursomes.append(randomFoursomes())
        allowedPairs   = 1
    return result

def tournamentTables(players, maxPair=1):
    rounds  = []    # list of foursome for each round (one foresome per table)
    paired  = Counter() # of player-player tuples (lowest payer number first)
    while True:
        roundTables = arrangeTables(players,maxPair,paired)
        if not roundTables: break
        shuffle(roundTables)
        rounds.append(roundTables)
        for foursome in roundTables:
            pairs  = combinations(foursome,2)
            paired = paired + Counter(pairs)
    return rounds

此版本将让您决定每个玩家愿意接受多少配对以达到更高的回合数。

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 名玩家组合。正如我所怀疑的那样，大部分时间都花在尝试（并且失败）找到第 6 轮解决方案上。这意味着，如果您在完成 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

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

这允许逻辑使用 3 的组合而不是剩余玩家列表中的 4 的组合。它还允许通过仅组合尚未与占据第一个位置的玩家配对的对手来提前过滤桌子的剩余玩家。

于 2019-03-11T22:21:20.003 回答