最佳拟合算法，可在回合中均匀放置对决

本文关键字：对决 算法 拟合 最佳 | 更新日期: 2023-09-27 18:35:05

我需要一种算法，它可以接受任意数量的匹配，如下所示，并按回合将它们平均分组，如果可能的话，每个人都参与一次。我按回合生成了以下 8 支和 3 支球队的比赛。我在填满我的回合时遇到了问题，并且留下了一个无法进入最后一轮的孤儿游戏。

现在回合是任意的，但正如你所知道的，每个参与者都可以在每一轮中找到（1，2，3，4，5，6，7，8）。现在这些对决可以删除或添加，并在下面生成后随机排序，因此需要均匀分布它们并在以后找到回合，我只是无法保存原始回合，因为游戏可以添加/更改/删除。

此算法应该是通用的，并且每次都进行最佳拟合。如果每支球队的对决数量不均匀，那么与其他球队相比，他们可能有额外的回合，这也需要考虑在内。这也需要高性能。

我正在寻找一些 C# .NET 或其他语言中的伪代码来了解如何完成此操作。

8支球队，每支球队10场比赛 

Round 1
1 vs 2
3 vs 4
5 vs 6
7 vs 8
Round 2
1 vs 3
2 vs 4
5 vs 7
6 vs 8
Round 3
1 vs 4
2 vs 3
5 vs 8
6 vs 7
Round 4
1 vs 5
2 vs 6
3 vs 7
4 vs 8
Round 5
1 vs 6
2 vs 5
3 vs 8
4 vs 7
Round 6
1 vs 7
2 vs 8
3 vs 5
4 vs 6
Round 7
1 vs 8
2 vs 7
3 vs 6
4 vs 5
Round 8
1 vs 2
3 vs 4
5 vs 6
7 vs 8
Round 9
1 vs 3
2 vs 4
5 vs 7
6 vs 8
Round 10
1 vs 4
2 vs 3
5 vs 8
6 vs 7

3支球队，每支球队2场比赛

Round 1
1 vs 2
Round 2
2 vs 3
Round 3
1 vs 3

最佳拟合算法，可在回合中均匀放置对决

如果需要更具体，则必须自定义代码。

班级团队：

class Team
{
    string name = "";
    List<Team> playedAgainst = new List<Team>();
    public string Name
    {
        get { return name; }
        set { name = value; }
    }
    public Team(string name)
    {
        this.name = name;
    }
    public void AddOpponent(Team opponent)
    {
        this.playedAgainst.Add(opponent);
    }
    public bool hasPlayedAgainst(Team opponent)
    {
        return playedAgainst.Contains(opponent);
    }
    public void Reset()
    {
        playedAgainst.Clear();
    }
    public override bool Equals(object obj)
    {
        if(!(obj is Team))
        return base.Equals(obj);
        Team t = (Team)obj;
        return t.name == name;
    }
    public override string ToString()
    {
        return name;
    }
}

班级团队对决：

class TeamMatchup
{
    List<Team> involvedTeams = new List<Team>();
    List<List<Team[]>> rounds = new List<List<Team[]>>();
    public void AddTeam(Team team)
    {
        involvedTeams.Add(team);
    }
    public void GenerateBattleRounds()
    {
        rounds = new List<List<Team[]>>();
        while(true)
        {
            List<Team[]> round = new List<Team[]>();
            foreach (Team team in involvedTeams)
            {
                if (!round.TrueForAll(battle => !battle.Contains(team)))
                    continue;
                Team team2 = involvedTeams.FirstOrDefault(t => t != team && !t.hasPlayedAgainst(team) && round.TrueForAll(battle => !battle.Contains(t)));
                if (team2 == null) //even count of teams
                    continue;
                team.AddOpponent(team2);
                team2.AddOpponent(team);
                round.Add(new Team[] { team, team2 });
            }
            if (round.Count == 0)
                break;
            rounds.Add(round);
        }
    }
    public override string ToString()
    {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < rounds.Count; i++)
        {
            sb.AppendLine("Round " + (i + 1));
            foreach (Team[] battle in rounds[i])
            {
                sb.AppendLine(battle[0] + " - " + battle[1]);
            }
        }
        return sb.ToString();
    }
}

用法：

        TeamMatchup matchup = new TeamMatchup();
        matchup.AddTeam(new Team("Team 1"));
        matchup.AddTeam(new Team("Team 2"));
        matchup.AddTeam(new Team("Team 3"));
        matchup.AddTeam(new Team("Team 4"));
        matchup.AddTeam(new Team("Team 5"));
        matchup.AddTeam(new Team("Team 6"));
        matchup.AddTeam(new Team("Team 7"));
        matchup.AddTeam(new Team("Team 8"));
        matchup.GenerateBattleRounds();
        textBox1.Text = matchup.ToString();

输出：

Round 1
Team 1 - Team 2
Team 3 - Team 4
Team 5 - Team 6
Team 7 - Team 8
Round 2
Team 1 - Team 3
Team 2 - Team 4
Team 5 - Team 7
Team 6 - Team 8
Round 3
Team 1 - Team 4
Team 2 - Team 3
Team 5 - Team 8
Team 6 - Team 7
Round 4
Team 1 - Team 5
Team 2 - Team 6
Team 3 - Team 7
Team 4 - Team 8
Round 5
Team 1 - Team 6
Team 2 - Team 5
Team 3 - Team 8
Team 4 - Team 7
Round 6
Team 1 - Team 7
Team 2 - Team 8
Team 3 - Team 5
Team 4 - Team 6
Round 7
Team 1 - Team 8
Team 2 - Team 7
Team 3 - Team 6
Team 4 - Team 5

编辑：

谁以及为什么你投票否决这个解决方案？这是对用户目标的第一个提示。如果提问者想要更详细的答案，他必须问更具体（或至少使用一个问号）。

相关文章：