c# - 最佳拟合算法以在回合中均匀放置对决

Question

我需要一种算法，它可以像您在下面看到的那样进行任意数量的比赛，并按回合对它们进行平均分组，如果可能的话，每个人都参加一次。我为 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

Answer 1

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

类(class)团队:

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

编辑:

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