我正在尝试开发一种算法，以生成我的家人每年举办的游戏比赛的时间表。我写了一个只能部分起作用的解决方案。似乎它适用于2 ^ x播放器，但在两者之间不起作用。
Parcheesi是一次只能由4个人参加的游戏，因此，我们将比赛安排为4个人（16、28、32等）的倍数。在第1轮中，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位玩家，它就会失败。第2轮中的牌桌“用完了”，并且无法将玩家33添加到尚未玩过某人的牌桌上。
我尝试过遍历后退，前进/后退，交替，随机化放置在桌子上的玩家以及其他玩家的列表，但是似乎没有任何效果。
在实践中，我们手动制定了此计划，效果很好。我想写这个程序是对我自己的挑战，但是被卡住了。
最佳答案
如果您想进行多轮而不重新配对，则您的人数必须是16以后的4的倍数。
例如，如果您在第一张桌子上有玩家1,2,3,4（无论您如何组织其他桌子），则第二轮将至少需要4张桌子（4位玩家中的每位），以确保这四个人不在同一张桌子上。您需要16个人来填写这四个表。那16个人应该允许您进行5轮比赛而无需重新配对。鉴于玩家1,2,3和4再也无法见面，因此他们将在剩下的回合中独占一张桌子。到那时，他们每个人还有12个人要与之对抗，如果您将其完美地混合在一起，那么每轮将有3个人参加，总共增加4轮（共5轮）。因此，与16个人一起做5轮是最好的。
[EDIT2]我最初认为需要16的倍数，但事实证明我在设置操作中犯了一个错误。您可以为20人进行多轮比赛。我在两个示例中都修复了它。
以下是一种蛮力方法，该方法使用回溯来查找不会重新配对任何人的四人组合。它使用集合来控制配对冲突，并使用itertools groups（）函数生成四人组（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位玩家的组合。正如我所怀疑的那样，大部分时间都花在尝试（和失败）寻找第六轮解决方案上。这意味着，如果您在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的组合工作。通过仅组合未与占据第一名的玩家配对的对手，还可以及早过滤剩余的玩家。
关于python - 4人锦标赛排程，Python，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/55109524/