给定一些约束计算所有可能的组合

Question

我正在尝试为个人项目解决这个算法问题。

本次锦标赛共有 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

Answer 1

您可以检查constraint satisfaction problem。这是关于SAT求解器或SMT求解器。

也许你的问题可以定义为CS问题

可以解决 CS 问题的示例库：

Z3 Theorem Prover。它用于 C++，但也有 Java、.Net、Python 等的包装器
OptaPlanner. Dedicated for Java. I think it's friendly to use. Documentation有全面的解释。
Choco. Also dedicated for Java. I think it's the simplest. Example usage for solving eight queens puzzle.

我知道我给你的是库，不是算法，但也许没有必要重新发明轮子。

Answer 2

这个问题是高度对称的让我把它写成更紧凑的形式

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...），并且都出现在 table 中，每组恰好出现一次。 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 所做的。

给定一些约束计算所有可能的组合

compute all possible combinations given some constrains

algorithm

performance

combinatorics

问题：

编辑：