c# - “牵线搭桥”算法？

Question

对于一个项目，我需要计算几个团队之间的比赛计划。

要求：

• 我有几个团队
• 所有球队都必须与其他球队交手一次（而且只有一次）
• 所有球队同时比赛

例如，对于 4teams（A、B、C 和 D），我希望能够计算出这个：

第1轮

• 甲对乙
• C与D

第二轮

• A与D
• 乙与丙

第三轮

• 甲与丙
• B 与 D

问题是，在 X 轮中有一些选择，这将使 X+1 轮中的任何比赛都无法进行（球队已经与其他球队交手）。

我想我可以使用一些回溯技术，但我正在寻找是否有这样的算法？

这将在 c# 中实现。

你知道如何做到这一点吗？

Answer 1

实际上答案在评论中提供的链接中 。更具体地说，这个答案。

它确实处理了 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

Answer 2

我认为你采取了错误的方式。我不是在每一轮都根据前一轮计算配对，而是首先使用一个简单的双循环进行所有可能的配对，然后按轮随机分配游戏。

由于每个玩家将玩完全相同数量的游戏，因此必须存在这种分布。

Answer 3

尝试循环。这是一个在进程之间共享时隙的简单调度算法，但这个问题让我想起了它。

编辑

现在这里是循环锦标赛的实现。如果我们有奇数队，我们必须插入一个虚拟队，否则会有一个没有对手的球队。由于轮数为偶数，总轮数为​​ (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() 应该细化，这是一种快速的方法。

Answer 4

我快速开始，使用简单的方法

1. 生成所有可能的游戏
2. 根据团队可用性将游戏分配到回合

这导致游戏的分布看起来有点“僵硬”。

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