对于一个项目，我需要计算几个团队之间的比赛计划。
要求：
- 我有几个团队
- 所有球队都必须与其他球队交手一次（而且只有一次）
- 所有球队同时比赛
例如，对于 4teams（A、B、C 和 D），我希望能够计算出这个：
第1轮
- 甲对乙
- C与D
第二轮
- A与D
- 乙与丙
第三轮
- 甲与丙
- B 与 D
问题是，在 X 轮中有一些选择，这将使 X+1 轮中的任何比赛都无法进行（球队已经与其他球队交手）。
我想我可以使用一些回溯技术，但我正在寻找是否有这样的算法？
这将在 c# 中实现。
你知道如何做到这一点吗？
问问题
3587 次
4 回答
3
它确实处理了 Round 的概念，只是它不是很明显。在该代码中，aTuple<string, string>代表一场比赛（包含两个团队名称的项目），aList<Tuple<string, string>>代表一轮（比赛的集合）。
该代码以 a 的形式返回 Rounds 的集合List<List<Tuple<string, string>>>。
我稍微重构了代码，以便在代码中Match和的概念Round更加明显。
这是Match和Round类：
public class Match
{
public string Team1 { get; set; }
public string Team2 { get; set; }
public Match(string team1, string team2)
{
Team1 = team1;
Team2 = team2;
}
public override string ToString()
{
return string.Format("{0} vs {1}", Team1, Team2);
}
}
public class Round
{
public List<Match> Matches { get; private set; }
public Round()
{
Matches = new List<Match>();
}
public override string ToString()
{
return String.Join(Environment.NewLine, Matches) + Environment.NewLine;
}
}
这里是神奇的代码（学分去Nagg）：
public static List<Round> ComputeFixtures(List<string> listTeam)
{
var result = new List<Round>();
var numberOfRounds = (listTeam.Count - 1);
var numberOfMatchesInARound = listTeam.Count / 2;
var teams = new List<string>();
teams.AddRange(listTeam.Skip(numberOfMatchesInARound).Take(numberOfMatchesInARound));
teams.AddRange(listTeam.Skip(1).Take(numberOfMatchesInARound - 1).ToArray().Reverse());
var numberOfTeams = teams.Count;
for (var roundNumber = 0; roundNumber < numberOfRounds; roundNumber++)
{
var round = new Round();
var teamIdx = roundNumber % numberOfTeams;
round.Matches.Add(new Match(teams[teamIdx], listTeam[0]));
for (var idx = 1; idx < numberOfMatchesInARound; idx++)
{
var firstTeamIndex = (roundNumber + idx) % numberOfTeams;
var secondTeamIndex = (roundNumber + numberOfTeams - idx) % numberOfTeams;
round.Matches.Add(new Match(teams[firstTeamIndex], teams[secondTeamIndex]));
}
result.Add(round);
}
return result;
}
以下是此代码的一些在线运行示例：
- 四支球队：http: //ideone.com/bTfld
- 六支球队：http: //ideone.com/fw6wE
- 十二支球队：http: //ideone.com/peIAI
于 2012-10-15T08:38:02.283 回答
2
我认为你采取了错误的方式。我不是在每一轮都根据前一轮计算配对，而是首先使用一个简单的双循环进行所有可能的配对，然后按轮随机分配游戏。
由于每个玩家将玩完全相同数量的游戏，因此必须存在这种分布。
于 2012-10-14T16:21:59.973 回答
1
尝试循环。这是一个在进程之间共享时隙的简单调度算法，但这个问题让我想起了它。
编辑
现在这里是循环锦标赛的实现。如果我们有奇数队，我们必须插入一个虚拟队，否则会有一个没有对手的球队。由于轮数为偶数，总轮数为 (NumberOfTeams-1)。一开始我们设置了第一轮：
ABCDEFGH
HGFEDCBA
所以，团队 A - H，团队 B - G，等等。
从现在开始，我们保持一个团队不变，例如 A。然后我们将 A_Side 团队从第二个位置移到右侧。最后一支队伍将进入位置 2。（ABCDEFGH 将是 AHBCDEFG）。请参阅 rotate_A_side() 递归方法（只是为了好玩）。
B_Sides 的一半向左移动。这将使 HGFED - GFE D.
由于球队选择是对称的（A 与 H 比赛，然后 H 与 A 比赛），B_Side 的上半部分是 A_Side 低部分球队的反向副本。因此，DCBA 将是 CBHA）。请参阅旋转_B_side()。
所以，第2轮是：
HBCDEFG _
GFED CBHA
要进行所有回合，只需重复上述移动步骤即可。见下一轮（）
这是实现算法的 ac# 类：
class Teams
{
private int[] A_Side;
private int[] B_Side;
public int[,] PlayingCounter;
public int RoundCounter = 1;
public bool DummyTeam = false; // ODD number of teams -> one team will no be able to play.
public bool NextRoundExists
{
get
{
return (RoundCounter < B_Side.Length-1);
}
}
public Teams(int NumberOfTeams)
{
if (NumberOfTeams % 2 != 0)
{
NumberOfTeams++; DummyTeam = true;
}
A_Side = new int[NumberOfTeams];
B_Side = new int[NumberOfTeams];
PlayingCounter = new int[NumberOfTeams,NumberOfTeams]; // Counting to see if alg is correct
int x,y;
for (x=0; x<NumberOfTeams; x++)
{
A_Side[x] = x + 1;
B_Side[NumberOfTeams-x-1]=x+1;
for (y=0;y<NumberOfTeams;y++)
{
PlayingCounter[x,y] = 0;
}
}
}
private void rotate_A_Side(int AtPos)
{
if (AtPos == 1)
{
int iO = A_Side[A_Side.Length - 1];
rotate_A_Side(AtPos+1);
A_Side[1] = iO;
}
else
{
if (AtPos < A_Side.Length - 1) { rotate_A_Side(AtPos + 1); }
A_Side[AtPos] = A_Side[AtPos - 1];
}
}
public void rotate_B_Side()
{
int i;
for (i = 0; i<B_Side.Length/2 ; i++)
{
B_Side[i] = B_Side[i + 1];
}
for (i = B_Side.Length / 2; i < B_Side.Length; i++)
{
B_Side[i] = A_Side[B_Side.Length/2 - (i -B_Side.Length/2 + 1) ];
}
}
public bool NextRound()
{
if (NextRoundExists)
{
RoundCounter++; // Next round
rotate_A_Side(1); // A side rotation
rotate_B_Side(); // B side rotation
LogRound(); // Update counters
return true;
}
else return false;
}
public void LogRound()
{
for (int x = 0; x < A_Side.Length; x++)
{
PlayingCounter[A_Side[x]-1, B_Side[x]-1]++;
PlayingCounter[B_Side[x]-1, A_Side[x]-1]++;
}
}
public string GetCounters()
{
string return_value = "";
for (int y = 0; y < A_Side.Length; y++)
{
for (int x = 0; x < A_Side.Length; x++)
{
return_value += String.Format(" {0:D3}", PlayingCounter[y, x]);
}
return_value += System.Environment.NewLine;
}
return return_value;
}
public string GetCurrentRound()
{
string Round = "Round #" + RoundCounter.ToString() + " ";
for (int x = 0; x < B_Side.Length; x++)
{
Round += String.Format("Team {0} - Team {1};", A_Side[x], B_Side[x]);
}
return Round;
}
}
从您的代码中，您可以像这样使用它：
Teams Rounds = new Teams(22);
if (Rounds.DummyTeam) {
// Anything to do if nober of teams is odd?
}
Rounds.LogRound(); // DEBUG - you can check number of matches ;-)
while (Rounds.NextRoundExists) // While we have next round...
{
Rounds.NextRound(); // ... generate the next
// round (team assignment)
// Your can tack using: Rounds.GetCurrentRound()
}
// If you want to see the number of matches, call Rounds.GetCounters();
6个团队给了我以下输出：
第一轮自动对焦；是 ; 光盘；直流; 乙; F A ;
第2轮AE；FD; 卑诗省; CB; 东风; 艺电;
第 3 轮 AD ; 欧共体；脸书；高炉; 行政长官; 大;
第四轮交流；D B ; 英孚；铁; BD ; 加利福尼亚州；
第 5 轮 AB ; CF; 德; 教育署；光纤通道；巴;
我用 A 替换了 Team 1，等等。
rotate_B_Side() 应该细化，这是一种快速的方法。
于 2012-10-14T17:24:06.300 回答
0
我快速开始，使用简单的方法
- 生成所有可能的游戏
- 根据团队可用性将游戏分配到回合
这导致游戏的分布看起来有点“僵硬”。
schedule_tournament(new List<string> { "A", "B", "C" });
schedule_tournament(new List<string> { "A", "B", "C", "D", });
schedule_tournament(new List<string> { "A", "B", "C", "D", "E" });
schedule_tournament(new List<string> { "A", "B", "C", "D", "E", "F" });
schedule_tournament(new List<string> { "A", "B", "C", "D", "E", "F", "G" });
...
private void schedule_tournament(List<string> teams)
{
List<string> games = new List<string>();
List<string> rounds = new List<string>();
// get all possible games
for (int i = 0; i < teams.Count; i++)
{
for (int j = i + 1; j < teams.Count; j++)
{
string game_name = string.Format("{0}{1}", teams[i], teams[j]);
if (!games.Contains(game_name)) games.Add(game_name);
}
}
// allocate games to rounds
for (int i = 0; i < games.Count; i++)
{
bool allocated = false;
for (int j = 0; j < rounds.Count; j++)
{
string team_1 = games[i].Substring(0, 1);
string team_2 = games[i].Substring(1, 1);
if (!rounds[j].Contains(team_1) && !rounds[j].Contains(team_2))
{
rounds[j] += " - " + games[i];
allocated = true;
break;
}
}
if (!allocated)
{
rounds.Add(games[i]);
}
}
Console.WriteLine("{0} teams, play {1} games in {2} rounds", teams.Count, games.Count, rounds.Count);
for (int i = 0; i < rounds.Count; i++) Console.WriteLine("Round {0}: {1}", i + 1, rounds[i]);
}
这个的输出是：
3 teams, play 3 games in 3 rounds
Round 1: AB
Round 2: AC
Round 3: BC
4 teams, play 6 games in 3 rounds
Round 1: AB - CD
Round 2: AC - BD
Round 3: AD - BC
5 teams, play 10 games in 7 rounds
Round 1: AB - CD
Round 2: AC - BD
Round 3: AD - BC
Round 4: AE
Round 5: BE
Round 6: CE
Round 7: DE
6 teams, play 15 games in 7 rounds
Round 1: AB - CD - EF
Round 2: AC - BD
Round 3: AD - BC
Round 4: AE - BF
Round 5: AF - BE
Round 6: CE - DF
Round 7: CF - DE
7 teams, play 21 games in 7 rounds
Round 1: AB - CD - EF
Round 2: AC - BD - EG
Round 3: AD - BC - FG
Round 4: AE - BF - CG
Round 5: AF - BE - DG
Round 6: AG - CE - DF
Round 7: BG - CF - DE
于 2012-10-15T16:14:24.247 回答