安排6种不同比赛类型的16队1v1比赛

Question

我接到了为一家公司的团队比赛制定时间表的任务。最初我认为这将是非常微不足道的，但我在想出一个有效的解决方案时遇到了一些麻烦。以下是需要满足的事实：

有16支队伍
有 6 种不同的 1v1 游戏可以玩
每支队伍必须参加所有 6 种比赛类型
没有两支球队可以互相比赛两次
一个团队可以玩 8 个 "rounds" 或 "time slots"。这意味着一支球队将有两轮休息并且没有比赛
任何游戏类型都不能在同一轮中玩两次

这不是循环赛，因为所有队伍都不会互相比赛。它有点类似于 Swiss Tournament，但具有所有团队都必须玩的多种游戏类型的限制。我正在努力找出正确的算法来确定这个时间表，任何有助于解决问题的帮助或信息都会很棒。

Answer 1

我认为你可以使用本地搜索来解决这个问题，但让我给你一个数学构造。

将16支队伍分成8支A队和8支B队。每支 A 队将参加除 2 支 B 队以外的所有比赛。每支 B 队将参加除 2 支 A 队之外的所有比赛。

此构造需要两个相互正交的 8x8 拉丁方，例如，

abcdehfg
badchegf
cdabgfhe
dcbafgeh
ehgfabdc
hefgbacd
fghedcab
gfehcdba

abcdefgh
cdabhgfe
efhgabdc
hgefcdba
dcbaghef
badcfehg
feghbacd
ghfedcab

按 A 队索引行，按 B 队索引列。第一个拉丁方的条目指定 activity，其中 A 队将与 B 队比赛。其中两个字母被视为休息。根据拉丁方的性质，每个团队都完成每个 activity 恰好一次（并休息两次）。

第二个拉丁方的条目表示 A 队何时与 B 队比赛（或双方休息）。根据拉丁方的性质，每个团队在每一轮中做一件事情。根据相互正交的拉丁方的性质，每个activity在每一轮中恰好出现一次。

在Python 3:

import string


def latin8a(i, j):
    return i ^ j


def latin8b(i, j):
    b = i >> 2
    return (i << 1) ^ (b << 3 | b << 1 | b) ^ j


a_teams = string.ascii_uppercase[:8]
b_teams = string.ascii_uppercase[8:16]
for i in range(8):
    print()
    print('Round', i + 1)
    for j in range(6):
        print(a_teams[latin8a(i, j)], 'vs', b_teams[latin8b(i, j)],
              'in game type', string.ascii_lowercase[j])

输出：

Round 1
A vs I in game type a
B vs J in game type b
C vs K in game type c
D vs L in game type d
E vs M in game type e
F vs N in game type f

Round 2
B vs K in game type a
A vs L in game type b
D vs I in game type c
C vs J in game type d
F vs O in game type e
E vs P in game type f

Round 3
C vs M in game type a
D vs N in game type b
A vs O in game type c
B vs P in game type d
G vs I in game type e
H vs J in game type f

Round 4
D vs O in game type a
C vs P in game type b
B vs M in game type c
A vs N in game type d
H vs K in game type e
G vs L in game type f

Round 5
E vs L in game type a
F vs K in game type b
G vs J in game type c
H vs I in game type d
A vs P in game type e
B vs O in game type f

Round 6
F vs J in game type a
E vs I in game type b
H vs L in game type c
G vs K in game type d
B vs N in game type e
A vs M in game type f

Round 7
G vs P in game type a
H vs O in game type b
E vs N in game type c
F vs M in game type d
C vs L in game type e
D vs K in game type f

Round 8
H vs N in game type a
G vs M in game type b
F vs P in game type c
E vs O in game type d
D vs J in game type e
C vs I in game type f

安排6种不同比赛类型的16队1v1比赛

Scheduling a 16-team 1v1 competition with 6 different game types

algorithm

combinations

combinatorics

schedule

sports-league-scheduling-problem