问题

我在考虑一种算法，将游戏分配给对手的配对，他们会玩这个游戏。

我有x个对手和y个游戏（我认为y应该是x - 1，但我不确定）
每个对手应该每场比赛都参加一次，如果可能的话，应该对每个对手进行一次比赛。

我想要的是一个分组配对的列表，分配给一个游戏。
总游戏数应该尽量少。

以4个对手“A，B，C，D”和3场比赛为例：

在这里，每个对手都与另一个对手比赛一次，每个对手都参加每场比赛一次。

尝试手动解决5名对手和4场比赛已经很复杂。

那么7名对手和6场比赛呢？
这是否可能？

我尝试手动解决这个问题，然后发现这太复杂了。

之后，我考虑了如何可能使用算法来解决它，但我想不出解决方案。
我想也许一个尝试最小化总游戏数的图算法可以有所帮助。

答案1

得分: 1

以下是翻译好的部分：

• 循环 Op1 遍历组（例如 A、B、C 等）
  • 循环 Op2 遍历组，从 Op1 + 1 开始（例如 B、C 等）
    • 循环 G 遍历游戏
      • 如果 Op1 和 Op2 都没有参加游戏 G
        • 在游戏 G 中分配 Op1 与 Op2
        • 从 G 循环中退出

以下是C++代码：

#include <string>
#include <fstream>
#include <sstream>
#include <iostream>
#include <vector>
#include <algorithm>

class cMatchMaker
{
public:
    void ParseCommand(int argc, char *argv[])
    {
        if (argc != 3)
            exit(1);
        groupCount = atoi(argv[1]);
        gameCount = atoi(argv[2]);
    }
    void ConstructGroups()
    {
        for (int kg = 0; kg < groupCount; kg++)
        {
            std::string s({'A' + kg});
            vGroup.push_back(s);
            vGroupHasPlayed.push_back({});
        }
    }
    void ConstructGames()
    {
        for (int kg = 0; kg < gameCount; kg++)
        {
            vGame.push_back(std::to_string(kg + 1));
        }
    }

    void MakeMatches()
    {
        // 遍历组
        for (kop1 = 0; kop1 < groupCount; kop1++)
        {
            // 遍历可能的对手
            for (kop2 = kop1 + 1; kop2 < groupCount; kop2++)
            {
                // 遍历游戏
                for (auto &game : vGame)
                {
                    // 检查两个组都没有参加游戏
                    if (!HasGameBeenPlayed(
                            game))
                    {
                        // 我们有一个比赛！
                        DisplayMatch(
                            game);

                        // 记住谁参加了哪场比赛
                        Remember(
                            game);

                        break;
                    }
                }
            }
        }
    }

private:
    int groupCount, gameCount;
    std::vector<std::string> vGroup, vGame;
    std::vector<std::vector<std::string>> vGroupHasPlayed;
    int kop1, kop2;

    bool HasGameBeenPlayed(
        const std::string &game)
    {
        if (std::find(
                vGroupHasPlayed[kop1].begin(),
                vGroupHasPlayed[kop1].end(),
                game) != vGroupHasPlayed[kop1].end())
            return true;
        if (std::find(
                vGroupHasPlayed[kop2].begin(),
                vGroupHasPlayed[kop2].end(),
                game) != vGroupHasPlayed[kop2].end())
            return true;
        return false;
    }

    void DisplayMatch(
        const std::string &game)
    {
        std::cout << " | " << vGroup[kop1]
                  << " | " << game << " | "
                  << vGroup[kop2] << " |\n";
    }

    void Remember(
        const std::string &game)
    {
        vGroupHasPlayed[kop1].push_back(game);
        vGroupHasPlayed[kop2].push_back(game);
    }
};

main(int argc, char *argv[])
{
    cMatchMaker theMatchMaker;

    theMatchMaker.ParseCommand(argc, argv);
    theMatchMaker.ConstructGroups();
    theMatchMaker.ConstructGames();
    theMatchMaker.MakeMatches();

    return 0;
}

以下是7和6的输出：

 | Op1 | 游戏 | Op2 |
| ---|---|---|
| A | 1 | B |
| A | 2 | C |
| A | 3 | D |
| A | 4 | E |
| A | 5 | F |
| A | 6 | G |
| B | 3 | C |
| B | 2 | D |
| B | 5 | E |
| B | 4 | F |
| C | 1 | D |
| C | 6 | E |
| C | 4 | G |
| D | 6 | F |
| D | 5 | G |
| E | 1 | F |
| E | 2 | G |
| F | 3 | G |

- LOOP Op1 over groups ( e.g. A,B,C,... )
- LOOP Op2 over groups starting at Op1 + 1 ( e.g B,C, ... )
- LOOP G over games
- IF neither Op1 nor Op2 has played game G
- ASSIGN Op1 v Op2 in game G
- BREAK from LOOP G

#include <string>
#include <fstream>
#include <sstream>
#include <iostream>
#include <vector>
#include <algorithm>
class cMatchMaker
{
public:
void ParseCommand(int argc, char *argv[])
{
if (argc != 3)
exit(1);
groupCount = atoi(argv[1]);
gameCount = atoi(argv[2]);
}
void ConstructGroups()
{
for (int kg = 0; kg < groupCount; kg++)
{
std::string s({'A' + kg});
vGroup.push_back(s);
vGroupHasPlayed.push_back({});
}
}
void ConstructGames()
{
for (int kg = 0; kg < gameCount; kg++)
{
vGame.push_back(std::to_string(kg + 1));
}
}
void MakeMatches()
{
// loop over groups
for (kop1 = 0; kop1 < groupCount; kop1++)
{
// loop over possible opponents
for (kop2 = kop1 + 1; kop2 < groupCount; kop2++)
{
// loop over games
for (auto &game : vGame)
{
// check neither group has played game
if (!HasGameBeenPlayed(
game))
{
// we have a match!
DisplayMatch(
game);
// remember who played what
Remember(
game);
break;
}
}
}
}
}
private:
int groupCount, gameCount;
std::vector<std::string> vGroup, vGame;
std::vector<std::vector<std::string>> vGroupHasPlayed;
int kop1, kop2;
bool HasGameBeenPlayed(
const std::string &game)
{
if (std::find(
vGroupHasPlayed[kop1].begin(),
vGroupHasPlayed[kop1].end(),
game) != vGroupHasPlayed[kop1].end())
return true;
if (std::find(
vGroupHasPlayed[kop2].begin(),
vGroupHasPlayed[kop2].end(),
game) != vGroupHasPlayed[kop2].end())
return true;
return false;
}
void DisplayMatch(
const std::string &game)
{
std::cout << " | " << vGroup[kop1]
<< " | " << game << " | "
<< vGroup[kop2] << " |\n";
}
void Remember(
const std::string &game)
{
vGroupHasPlayed[kop1].push_back(game);
vGroupHasPlayed[kop2].push_back(game);
}
};
main(int argc, char *argv[])
{
cMatchMaker theMatchMaker;
theMatchMaker.ParseCommand(argc, argv);
theMatchMaker.ConstructGroups();
theMatchMaker.ConstructGames();
theMatchMaker.MakeMatches();
return 0;
}