我正试图为个人项目解决这个算法问题。
- 本届锦标赛共有8名选手
- 他们玩2vs2
- 同时进行两场比赛(因此所有8名球员都在比赛(
- 每个球员必须与所有其他球员一起打7场比赛(在同一支球队中(
- 比赛结束时，每个选手打了7场比赛
- 锦标赛共有14场比赛
- 比赛的排列不算作新的比赛。(即锦标赛被定义为一组比赛(
这是一个有玩家A、B、C、D、E、F、G、H:的锦标赛示例
Match 1 : A, B VS C, D. Score = ____ : ____
Match 2 : E, F VS H, G. Score = ____ : ____
Match 3 : C, A VS B, D. Score = ____ : ____
Match 4 : E, G VS H, F. Score = ____ : ____
Match 5 : A, D VS C, B. Score = ____ : ____
Match 6 : H, E VS F, G. Score = ____ : ____
Match 7 : E, A VS B, F. Score = ____ : ____
Match 8 : C, G VS H, D. Score = ____ : ____
Match 9 : A, F VS E, B. Score = ____ : ____
Match 10 : H, C VS D, G. Score = ____ : ____
Match 11 : A, G VS H, B. Score = ____ : ____
Match 12 : C, E VS D, F. Score = ____ : ____
Match 13 : H, A VS B, G. Score = ____ : ____
Match 14 : C, F VS E, D. Score = ____ : ____
注意，Match i和Match i+1同时播放if i%2==1
问题：
有多少不同的锦标赛是可能的？这些锦标赛是什么？
我尝试了一种蛮力的方法，但太慢了。有更好的算法吗？
编辑：
欢迎使用代码。尤其是python
这个问题是高度对称的让我用更紧凑的形式写它
AB CD + EF GH
AC BD + EG FH
AD BC + EH FG
AE BF + CG DH
AF BE + CH DG
AG BH + CE DF
AH BG + CF DE
对于8名球员，有28支可能由两人组成的球队(AB、AC、AD…(，所有球队都出现在表格中，每支球队只出现一次。AB和BA是同一支球队，我会选择第一种形式，因为它是按字母顺序排列的。AB CD和CD AB是相同的匹配，我会选择第一种形式。AB CD+EF GH和EF GH+AB CD只是匹配的排列，我会选第一种形式
AB __ + __ __
AC __ + __ __
AD __ + __ __
AE __ + __ __
AF __ + __ __
AG __ + __ __
AH __ + __ __
以这种方式，每行包含全部8个字母，每个字母恰好一次。这可以很容易地强行进行，计算大约需要15秒(无需将组合写入控制台(，结果为10034775
static bool SolutionIsOK(string[,] matchesTuples)
{
for (int i = 1; i < 7; ++i)
{
for (int j = 0; j < i; ++j)
{
string a1 = matchesTuples[j, 2];
string a2 = matchesTuples[i, 2];
if (a1[0] > a2[0] || a1[0] == a2[0] && a1[1] > a2[1])
{
string b1 = matchesTuples[j, 3];
string b2 = matchesTuples[i, 3];
int check1 = (1 << (a1[0] - 'A')) |
(1 << (a1[1] - 'A')) |
(1 << (b1[0] - 'A')) |
(1 << (b1[1] - 'A'));
int check2 = (1 << (a2[0] - 'A')) |
(1 << (a2[1] - 'A')) |
(1 << (b2[0] - 'A')) |
(1 << (b2[1] - 'A'));
if (check1 == check2) { return false; }
}
}
}
return true;
}
static void WriteSolution(string[,] matchesTuples)
{
for (int i = 0; i < 7; ++i)
{
Console.WriteLine(matchesTuples[i, 0] + " " + matchesTuples[i, 1] + " + "
+ matchesTuples[i, 2] + " " + matchesTuples[i, 3]);
}
Console.WriteLine("------------------------------");
}
static int counter = 0;
static void placeTeam(int level, string[] teams, string[,] matchesTuples, bool[,] presentPlayers)
{
if (level == teams.Length)
{
if (!SolutionIsOK(matchesTuples)) { return; };
WriteSolution(matchesTuples);
counter++; // solution found
return;
}
string team = teams[level++];
for (int i = 0; i < 7; ++i)
{
if (presentPlayers[i, team[0] - 'A']
|| presentPlayers[i, team[1] - 'A'])
{
continue;
}
presentPlayers[i, team[0] - 'A'] = true;
presentPlayers[i, team[1] - 'A'] = true;
for (int j = 1; j < 4; ++j)
{
if (matchesTuples[i, j] != null) { continue; }
if (j == 3 && (matchesTuples[i, 2] == null)) { continue; }
matchesTuples[i, j] = team;
placeTeam(level, teams, matchesTuples, presentPlayers);
matchesTuples[i, j] = null;
}
presentPlayers[i, team[0] - 'A'] = false;
presentPlayers[i, team[1] - 'A'] = false;
}
}
static void Main(string[] args)
{
string[,] matchesTuples = new string[7, 4]; // AE BF + CG DH
bool[,] presentPlayers = new bool[7, 8]; // ABCDEFGH
string[] teams = new string[28]; // AB, AC, AD, ..., BC, BD, ..., GH
int i = 0;
for (char c1 = 'A'; c1 < 'H'; ++c1)
{
for (char c2 = c1; ++c2 <= 'H';)
{
teams[i] = c1.ToString() + c2;
if (c1 == 'A')
{
matchesTuples[i, 0] = teams[i];
presentPlayers[i, c1 - 'A'] = true;
presentPlayers[i, c2 - 'A'] = true;
}
++i;
}
}
placeTeam(7, teams, matchesTuples, presentPlayers);
Console.WriteLine("Found " + counter);
Console.ReadKey();
}
唯一棘手的部分是CCD_ 4函数。它解决了最后一个未解决的对称性。这两种情况相同：
AC BD + EG FH
AD BC + EH FG
AC BD + EH FG
AD BC + EG FH
因为第二个匹配只是被置换的。只有当第二场比赛包含相同的4个人时，才能对其进行置换。这种情况可以检测到，我们只能选择按字母顺序排列的情况。这正是SolutionIsOK所做的。
您可以检查约束满足问题。它是关于SAT求解器或SMT求解器。
也许你的问题可以定义为CS问题。
可以解决CS问题的示例库：
- Z3定理证明。它是针对C++的，但也有针对Java、.Net、Python等的包装器
- OptaPlanner。专用于Java。我认为它使用起来很友好。文件有全面的解释
- 乔科。也专门用于Java。我认为这是最简单的。解决八皇后难题的示例用法
我知道我给你的是库，而不是算法，但也许没有必要重新发明轮子。