体育比赛时间表与变化的对

Question

假设有 8 名选手参加沙滩排球比赛。比赛进行 2 对 2。

作为组织者，我想为具有以下规则的玩家生成时间表：

每个玩家和每个人一起玩（每个玩家 7 场比赛）
每个玩家与每个玩家对战两次

因此计划将开始，例如：

round 1 
player1 + player2 vs player3 + player4
player5 + player6 vs player7 + player8

round2
player1 + player3 vs player2 + player5
player4 + player7 vs player6 + player8

round3
player1 + player4 vs player2 + player3
player5 + player8 vs player6 + player7

etc

通过上面的例子让我们想想player1。他一直在和玩家 (2,3,4) 一起比赛，所以他和玩家 (5,6,7,8) 一起剩下的比赛

他的对手是：

Player3 (twice)
Player4
Player2 (twice)
Player5

所以剩下的 4 场比赛（选手 1）应该与选手 5、6、7、8 一起比赛，对手不能是选手 3 或选手 2（因为你已经和他们打过两次）

我在这里看到了很好的例子 How to automatically generate a sports league schedule and wikipedia article about round robin https://en.wikipedia.org/wiki/Round-robin_tournament（Richard Schurig（1886 年）对配对表的原始构造）可以很好地生成比赛，但与某些球员的比赛将超过两场.

非常感谢任何帮助！

Answer 1

是的，这可以借助有限域 F₈ 来完成。我们用 F₈ 的元素之一来识别每个玩家。设 t 和 p 是 F₈ 的任何不同的非零元素。在 F₈ ∖ {0}（七个元素）中的 r 回合 r 中，玩家 x 有 x + r t 作为队友和 x + r p 和 x + r p + r t作为对手。

因为 x + r t + r t = x 和 x + r p + r t + r t = x + r p 在一个领域的特征2、每一轮每个选手只有一个队友，他们的两个对手都是队友。对于一对玩家 x 和 y，他们作为队友的回合是唯一确定的，因为等式 x + r t = y（等价于x = y + r t）只有一个解。类似的推理说明了为什么每个玩家都在恰好两轮中对抗其他玩家。

F8 = {
    (0, 0, 0): "a",
    (1, 0, 0): "b",
    (0, 1, 0): "c",
    (1, 1, 0): "d",
    (0, 0, 1): "e",
    (1, 0, 1): "f",
    (0, 1, 1): "g",
    (1, 1, 1): "h",
}


def f8_times(p, q):
    pq = (
        p[0] & q[0],
        (p[0] & q[1]) ^ (p[1] & q[0]),
        (p[0] & q[2]) ^ (p[1] & q[1]) ^ (p[2] & q[0]),
        (p[1] & q[2]) ^ (p[2] & q[1]),
        p[2] & q[2],
    )
    return (pq[0] ^ pq[3], pq[1] ^ pq[3] ^ pq[4], pq[2] ^ pq[4])


for a in F8:
    if any(a):
        print("{}{} vs {}{}; {}{} vs {}{}".format(*(F8[f8_times(a, b)] for b in F8)))

输出：

ab vs cd; ef vs gh
ac vs eg; db vs hf
ad vs gf; he vs bc
ae vs dh; gc vs fb
af vs be; ch vs dg
ag vs hb; fd vs ce
ah vs fc; bg vs ed

体育比赛时间表与变化的对

Sports tournament schedule with changing pairs

algorithm

math

schedule

tournament

sports-league-scheduling-problem