组和游戏算法

huangapple
go评论77阅读模式
英文:

Group and Game Algorithm

问题

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

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

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

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

对手1 游戏 对手2
A 1 B
A 2 C
A 3 D
B 2 C
B 3 D
C 1 D

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

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

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

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

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

英文:

I am thinking of an algorithm that assign games to pairs of opponents which play the game.

I have x opponents and y games (I think y should be x - 1, but I am not sure)
Every opponent should play each game once and if possible play against every opponent once.

What I want is a list of group pairings assigned to a game.
The number of games overall should be minimal.

An example with 4 opponents A, B, C, D and 3 games:

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

Here, each opponent plays against another opponent exactly once, and every opponent plays each game exactly once.

Trying that manually for 5 opponents and 4 games already gets complex.

How about 7 opponents and 6 games?
Is that possible at all?

I tried that to solve the problem manually, then I found out that this is too complex.

After that I thought about how I could maybe solve it using an algorithm, but I could not come up with a solution.
I thought maybe a graph algorithm which tries to minimize the overall games count could help.

答案1

得分: 1

以下是翻译好的部分：

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

以下是C++代码：

  1. #include <string>
  2. #include <fstream>
  3. #include <sstream>
  4. #include <iostream>
  5. #include <vector>
  6. #include <algorithm>
  8. class cMatchMaker
  9. {
  10. public:
  11.     void ParseCommand(int argc, char *argv[])
  12.     {
  13.         if (argc != 3)
  14.             exit(1);
  15.         groupCount = atoi(argv[1]);
  16.         gameCount = atoi(argv[2]);
  17.     }
  18.     void ConstructGroups()
  19.     {
  20.         for (int kg = 0; kg < groupCount; kg++)
  21.         {
  22.             std::string s({'A' + kg});
  23.             vGroup.push_back(s);
  24.             vGroupHasPlayed.push_back({});
  25.         }
  26.     }
  27.     void ConstructGames()
  28.     {
  29.         for (int kg = 0; kg < gameCount; kg++)
  30.         {
  31.             vGame.push_back(std::to_string(kg + 1));
  32.         }
  33.     }
  35.     void MakeMatches()
  36.     {
  37.         // 遍历组
  38.         for (kop1 = 0; kop1 < groupCount; kop1++)
  39.         {
  40.             // 遍历可能的对手
  41.             for (kop2 = kop1 + 1; kop2 < groupCount; kop2++)
  42.             {
  43.                 // 遍历游戏
  44.                 for (auto &game : vGame)
  45.                 {
  46.                     // 检查两个组都没有参加游戏
  47.                     if (!HasGameBeenPlayed(
  48.                             game))
  49.                     {
  50.                         // 我们有一个比赛！
  51.                         DisplayMatch(
  52.                             game);
  54.                         // 记住谁参加了哪场比赛
  55.                         Remember(
  56.                             game);
  58.                         break;
  59.                     }
  60.                 }
  61.             }
  62.         }
  63.     }
  65. private:
  66.     int groupCount, gameCount;
  67.     std::vector<std::string> vGroup, vGame;
  68.     std::vector<std::vector<std::string>> vGroupHasPlayed;
  69.     int kop1, kop2;
  71.     bool HasGameBeenPlayed(
  72.         const std::string &game)
  73.     {
  74.         if (std::find(
  75.                 vGroupHasPlayed[kop1].begin(),
  76.                 vGroupHasPlayed[kop1].end(),
  77.                 game) != vGroupHasPlayed[kop1].end())
  78.             return true;
  79.         if (std::find(
  80.                 vGroupHasPlayed[kop2].begin(),
  81.                 vGroupHasPlayed[kop2].end(),
  82.                 game) != vGroupHasPlayed[kop2].end())
  83.             return true;
  84.         return false;
  85.     }
  87.     void DisplayMatch(
  88.         const std::string &game)
  89.     {
  90.         std::cout << " | " << vGroup[kop1]
  91.                   << " | " << game << " | "
  92.                   << vGroup[kop2] << " |\n";
  93.     }
  95.     void Remember(
  96.         const std::string &game)
  97.     {
  98.         vGroupHasPlayed[kop1].push_back(game);
  99.         vGroupHasPlayed[kop2].push_back(game);
  100.     }
  101. };
  103. main(int argc, char *argv[])
  104. {
  105.     cMatchMaker theMatchMaker;
  107.     theMatchMaker.ParseCommand(argc, argv);
  108.     theMatchMaker.ConstructGroups();
  109.     theMatchMaker.ConstructGames();
  110.     theMatchMaker.MakeMatches();
  112.     return 0;
  113. }

以下是7和6的输出：

  1.  | Op1 | 游戏 | Op2 |
  2. | ---|---|---|
  3. | A | 1 | B |
  4. | A | 2 | C |
  5. | A | 3 | D |
  6. | A | 4 | E |
  7. | A | 5 | F |
  8. | A | 6 | G |
  9. | B | 3 | C |
  10. | B | 2 | D |
  11. | B | 5 | E |
  12. | B | 4 | F |
  13. | C | 1 | D |
  14. | C | 6 | E |
  15. | C | 4 | G |
  16. | D | 6 | F |
  17. | D | 5 | G |
  18. | E | 1 | F |
  19. | E | 2 | G |
  20. | F | 3 | G |
英文: 
  1. - LOOP Op1 over groups ( e.g. A,B,C,... )
  2. - LOOP Op2 over groups starting at Op1 + 1 ( e.g B,C, ... )
  3. - LOOP G over games
  4. - IF neither Op1 nor Op2 has played game G
  5. - ASSIGN Op1 v Op2 in game G
  6. - BREAK from LOOP G

Here is the C++ code

  1. #include &lt;string&gt;
  2. #include &lt;fstream&gt;
  3. #include &lt;sstream&gt;
  4. #include &lt;iostream&gt;
  5. #include &lt;vector&gt;
  6. #include &lt;algorithm&gt;
  7. class cMatchMaker
  8. {
  9. public:
  10. void ParseCommand(int argc, char *argv[])
  11. {
  12. if (argc != 3)
  13. exit(1);
  14. groupCount = atoi(argv[1]);
  15. gameCount = atoi(argv[2]);
  16. }
  17. void ConstructGroups()
  18. {
  19. for (int kg = 0; kg &lt; groupCount; kg++)
  20. {
  21. std::string s({&#39;A&#39; + kg});
  22. vGroup.push_back(s);
  23. vGroupHasPlayed.push_back({});
  24. }
  25. }
  26. void ConstructGames()
  27. {
  28. for (int kg = 0; kg &lt; gameCount; kg++)
  29. {
  30. vGame.push_back(std::to_string(kg + 1));
  31. }
  32. }
  33. void MakeMatches()
  34. {
  35. // loop over groups
  36. for (kop1 = 0; kop1 &lt; groupCount; kop1++)
  37. {
  38. // loop over possible opponents
  39. for (kop2 = kop1 + 1; kop2 &lt; groupCount; kop2++)
  40. {
  41. // loop over games
  42. for (auto &amp;game : vGame)
  43. {
  44. // check neither group has played game
  45. if (!HasGameBeenPlayed(
  46. game))
  47. {
  48. // we have a match!
  49. DisplayMatch(
  50. game);
  51. // remember who played what
  52. Remember(
  53. game);
  54. break;
  55. }
  56. }
  57. }
  58. }
  59. }
  60. private:
  61. int groupCount, gameCount;
  62. std::vector&lt;std::string&gt; vGroup, vGame;
  63. std::vector&lt;std::vector&lt;std::string&gt;&gt; vGroupHasPlayed;
  64. int kop1, kop2;
  65. bool HasGameBeenPlayed(
  66. const std::string &amp;game)
  67. {
  68. if (std::find(
  69. vGroupHasPlayed[kop1].begin(),
  70. vGroupHasPlayed[kop1].end(),
  71. game) != vGroupHasPlayed[kop1].end())
  72. return true;
  73. if (std::find(
  74. vGroupHasPlayed[kop2].begin(),
  75. vGroupHasPlayed[kop2].end(),
  76. game) != vGroupHasPlayed[kop2].end())
  77. return true;
  78. return false;
  79. }
  80. void DisplayMatch(
  81. const std::string &amp;game)
  82. {
  83. std::cout &lt;&lt; &quot; | &quot; &lt;&lt; vGroup[kop1]
  84. &lt;&lt; &quot; | &quot; &lt;&lt; game &lt;&lt; &quot; | &quot;
  85. &lt;&lt; vGroup[kop2] &lt;&lt; &quot; |\n&quot;;
  86. }
  87. void Remember(
  88. const std::string &amp;game)
  89. {
  90. vGroupHasPlayed[kop1].push_back(game);
  91. vGroupHasPlayed[kop2].push_back(game);
  92. }
  93. };
  94. main(int argc, char *argv[])
  95. {
  96. cMatchMaker theMatchMaker;
  97. theMatchMaker.ParseCommand(argc, argv);
  98. theMatchMaker.ConstructGroups();
  99. theMatchMaker.ConstructGames();
  100. theMatchMaker.MakeMatches();
  101. return 0;
  102. }

Here is the output for 7 and 6

Op1 Game 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

huangapple
  • 本文由 发表于 2023年2月18日 03:22:44
  • 转载请务必保留本文链接：https://go.coder-hub.com/75488480.html
  • algorithm
  • graph-theory
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定