计算给定一些约束的所有可能的组合
提问于 2020-11-06 14:01:12
我试图为一个个人项目解决这个算法问题。
- 在这次比赛中有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
问题：
有多少不同的比赛是可能的？这些比赛是什么？
我试过一种蛮力的方法，但太慢了。有没有更好的算法？
编辑：
密码是欢迎的。特别是蟒蛇
回答 2
Stack Overflow用户
回答已采纳
发布于 2020-11-06 18:58:48
这个问题是高度对称的，让我把它写成更紧凑的形式。
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只是配对的排列，我会选择第一种形式。在所有这些情况下，我们将问题简化为在此模式中填充21个单词。
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();
}唯一棘手的部分是SolutionIsOK函数。它解决了最后一个未被解决的对称性。这两种情况是平等的：
AC BD + EG FH
AD BC + EH FG
AC BD + EH FG
AD BC + EG FH因为第二次匹配只发生了变异。只有当这些匹配包含相同的4个人时，才能进行第二次匹配。可以检测到这种情况，我们只能选择按字母顺序排列的情况。这正是SolutionIsOK所做的。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/64722148
复制
![[操作系统]磁盘调度算法](https://ask.qcloudimg.com/http-save/yehe-2504969/8yo2s12i06.png)
腾讯云开发者
