排球运动员组合

Question

一些背景:
在排球中,球员在水池中进行比赛以确定排名.球队是一对球员.比赛是一对球员与另一对球员.对于这个例子,我们假设只有一个球场可以进行比赛,当球员没有比赛时,他们坐着/等待.池中玩家的数量将在4到7之间.如果池中有8个玩家,他们只会将其分成2个4个池.

我想计算最少的比赛数量,以便每个球员与其他球员一起比赛.

例如,一个4人游戏池将拥有以下团队:

import itertools
players = [1,2,3,4]
teams = [t for t in itertools.combinations(players,2)]
print 'teams:'
for t in teams:
    print t

输出:

teams:
(1, 2)
(1, 3)
(1, 4)
(2, 3)
(2, 4)
(3, 4)

和比赛数量:

matches = []
for match in itertools.combinations(teams,2):
    # A player cannot be on both teams at the same time
    if set(match[0]) & set(match[1]) == set():
        matches.append(match)

for match in matches:
    print match

输出:

((1, 2), (3, 4))
((1, 3), (2, 4))
((1, 4), (2, 3))

这是正确的,但是当我向池中添加第5个玩家时,此算法会中断:

((1, 2), (3, 4))
((1, 2), (3, 5))
((1, 2), (4, 5))
((1, 3), (2, 4))
((1, 3), (2, 5))
((1, 3), (4, 5))
((1, 4), (2, 3))
((1, 4), (2, 5))
((1, 4), (3, 5))
((1, 5), (2, 3))
((1, 5), (2, 4))
((1, 5), (3, 4))
((2, 3), (4, 5))
((2, 4), (3, 5))
((2, 5), (3, 4))

这些团队多次重复.

我试图保留一个可以玩的团队列表,但算法结果是贪婪的.我的意思是,当它到达(1,5)球队时,所有其他球队[(2,3),(2,4),(3,4)]已经打过,而且(1,5)永远不会得到玩.

我在找什么:

((1,2), (3,4)) (player 5 waits)
((1,3), (2,5)) (player 4 waits)
((1,4), (3,5)) (player 2 waits)
((1,5), (4,2)) (player 3 waits)
((2,3), (4,5)) (player 1 waits)

是否更容易为每个池大小手动计算,或者这可以在python中轻松完成？

谢谢您的帮助!

---

编辑:删除了Python标记.任何语言都足够了,我可以将它转换为Python.

Answer 1

必须有更好的方法来做到这一点，但这是一个开始：

import itertools
import operator
from copy import deepcopy as clone

def getPossibleOpponents(numPlayers):
    matches = list(itertools.combinations(itertools.combinations(range(1,numPlayers+1), 2), 2))
    possibleMatches = [match for match in matches if len(set(itertools.chain.from_iterable(match)))==4]
    answer, playedTeams = {}, set()
    opponents = {}
    for team, teams in itertools.groupby(possibleMatches, key=operator.itemgetter(0)):
        playedTeams.add(team)
        opponents[team] = [t for t in next(teams) if t!=team]

    return opponents

def updateOpponents(opponents, playedTeams):
    for team in playedTeams:
        if team in opponents:
            opponents.pop(team)
    for k,v in opponents.items():
        opponents[k] = [team for team in v if team not in playedTeams]

def teamSeatings(opponents, answer=None):
    if answer is None:
        answer = {}
    if not len(opponents):
        if not(len(answer)):
            return None
        print(answer)
            sys.exit(0)

    for k,v in opponents.items():
        if not v:
            return None

        newOpponents = clone(opponents)
        for away in opponents[k]:
            if k in newOpponents:
                newOpponents.pop(k)
            answer[k] = away
            updateOpponents(newOpponents, {itertools.chain.from_iterable(i[0] for i in answer.items())})
            teamSeatings(newOpponents, answer)

if __name__ == "__main__":
    opps = getPossibleOpponents(5)
    teamSeatings(opps)