分组和游戏算法

Question

分组和游戏算法

algorithmgraph-theory

4

我正在考虑一种算法，将游戏分配给玩游戏的对手。

我有x个对手和y个游戏（我认为y应该是x-1，但我不确定）每个对手都应该玩一次每个游戏，并且如果可能的话，与每个对手玩一次。

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

以下是一个4个对手A、B、C、D和3个游戏的示例：

Opp1	Game	Opp2
A	1	B
A	2	C
A	3	D
B	2	C
B	3	D
C	1	D

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

如果针对5个对手和4场比赛手动尝试已经很复杂了。

那么对于7个对手和6场比赛呢？这有可能吗？

我曾试图手动解决这个问题，但后来发现这太过复杂了。

然后我考虑如何使用算法来解决它，但我无法想出解决方案。我想也许一个图形算法可以尝试减少整体游戏数量。

- Manuel Kroiß

请澄清您所说的“组”的含义。在您的表格中，C在两个组中，这很令人困惑。 - ravenspoint

一个有4个组的例子。你的例子似乎只有2个组！ - ravenspoint

1

@ravenspoint 我认为他们的意思是一个组对另一个组进行对称比赛。这里，A、B、C和D是这些组。 - Berthur

1

@Berthur 看起来很有道理。楼主仍需要确认和澄清。也许表格列应该标注为“对手1”和“对手2”? - ravenspoint

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- ravenspoint · Accepted Answer

- 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

这里是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()
    {
        // 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;
}

这是 7 和 6 的输出

操作1	游戏	操作2
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