C#中的循环赛算法

Round Robin Tournament algorithm in C#

提问by Polo

I am having some trouble to achieve this little round robinproject. What i try to do is to generate a preview calendar of games

我在实现这个小循环项目时遇到了一些麻烦。我尝试做的是生成游戏的预览日历

then I want to output;

然后我想输出；

day 1: Team 1 vs Team 2; Team 3 vs Team 4; Team 5vs Team 6;

第 1 天：团队 1 对团队 2；3队对4队；5队vs 6队；

day 2 Team 1 vs Team 4; Team 6 vs Team 3; Team 2 vs Team 5;

第 2 天 1 队 vs 4 队；6队对3队；2队对5队；

till the end of the championship;

直到锦标赛结束；

Here is the code i've got so far but i'm having trouble to let the first team fixed while the rest of the array rotates...:

这是我到目前为止的代码，但我无法在阵列的其余部分旋转时让第一个团队固定...：

static void Main(string[] args)
   {
        string[] ListTeam = new string[] {"Equipe1", "Equipe2", "Equipe3", "Equipe4", "Equipe5", "Equipe6"};
        IList<Match> ListMatch = new List<Match>();
        it NumberOfDays = (ListTeam.Count()-1);
        int y = 2;

        for (int i = 1; i <= NumberOfDays; i++)
        {
            Console.WriteLine("\nDay {0} : \n",i);
            Console.WriteLine(ListTeam[0].ToString() + " VS " + ListTeam[i].ToString());

            for (y =ListTeam.Count(); y>0 ; y--)
            {
                Console.WriteLine(ListTeam[y].ToString() + " VS " + ListTeam[y+1].ToString());
                y++;
            }

        }
    }

EDIT: I found a code sample in java buti cant translate it...

编辑：我在 Java 中找到了一个代码示例，但我无法翻译它...

采纳答案by paracycle

This should be easy enough to do using modular arithmetic:

这应该很容易使用模块化算法来完成：

UPDATE 2:(As promised correct algorithm)

更新2：（如承诺的正确算法）

public void ListMatches(List<string> ListTeam)
{
    if (ListTeam.Count % 2 != 0)
    {
        ListTeam.Add("Bye");
    }

    int numDays = (numTeams - 1);
    int halfSize = numTeams / 2;

    List<string> teams = new List<string>();

    teams.AddRange(ListTeam.Skip(halfSize).Take(halfSize));
    teams.AddRange(ListTeam.Skip(1).Take(halfSize -1).ToArray().Reverse());

    int teamsSize = teams.Count;

    for (int day = 0; day < numDays; day++)
    {
        Console.WriteLine("Day {0}", (day + 1));

        int teamIdx = day % teamsSize;

        Console.WriteLine("{0} vs {1}", teams[teamIdx], ListTeam[0]);

        for (int idx = 1; idx < halfSize; idx++)
        {               
            int firstTeam = (day + idx) % teamsSize;
            int secondTeam = (day  + teamsSize - idx) % teamsSize;
            Console.WriteLine("{0} vs {1}", teams[firstTeam], teams[secondTeam]);
        }
    }
}

which would print each day's team matches.

这将打印每天的团队比赛。

Let me quickly try to explain how the algorithm works:

让我快速尝试解释算法的工作原理：

I noticed that since we are rotating all the teams except the first one, if we put all the teams in an array except the first one, then we should just read off the first team from that array using index offset based on the day and doing modular arithmetic to wrap around correctly. In practice we would be treating that array as infinitely repeating in both directions and we would be sliding our view incrementally to right (or to the left).

我注意到，由于我们正在轮换除第一个团队之外的所有团队，如果我们将除第一个团队之外的所有团队放在一个数组中，那么我们应该使用基于日期的索引偏移量从该数组中读取第一个团队并执行模算术正确环绕。在实践中，我们会将该数组视为在两个方向上无限重复，并且我们会逐渐向右（或向左）滑动我们的视图。

There is one snag, however, and that is the fact that we have to order the teams in a very particular way for this to work correctly. Otherwise, we do not get the correct rotation. Because of this we need to read of the matching second team in a very peculiar way as well.

然而，有一个障碍，那就是我们必须以一种非常特殊的方式对团队进行排序，以使其正常工作。否则，我们不会得到正确的旋转。因此，我们也需要以一种非常特殊的方式阅读匹配的第二支球队。

The correct way to prepare your list is as follows:

准备清单的正确方法如下：

• Never put the first team (Team#1) in the list.
• Take the last half of the team list and put them in the front of the list.
• Take the first half of the list, reverse it and put them in the list (but not Team#1).

• 切勿将第一支球队（Team#1）放入列表中。
• 将团队列表的后半部分放在列表的前面。
• 取列表的前半部分，将其反转并将它们放入列表中（但不是 Team#1）。

Now, the correct way to read off the list is as follow:

现在，读取列表的正确方法如下：

• For each day, increment the first index you are looking at by 1.
• For the first team that you see at that location, match that team with Team#1.
• For the next team in the list ((day + idx) % numDays), we would normally match it with the team that is offset by half the number of teams minus 1 (minus 1 because we dealt with the first match ourselves). However, since the second half of our list was prepared by reverting, we need to match that offset in the reverted second half of the list. A simpler way to do is to observe that in this is equivalent to matching the same index but from the end of the list. Given the current dayoffset that is (day + (numDays - idx)) % numDays.

• 对于每一天，将您正在查看的第一个索引增加1。
• 对于您在该位置看到的第一支球队，将该球队与 Team#1 匹配。
• 对于列表中的下一支球队 ( (day + idx) % numDays)，我们通常会将其与球队数量减去一半减去 1（减去 1，因为我们自己处理第一场比赛）所抵消的球队进行匹配。然而，由于我们的列表的后半部分是通过恢复准备的，我们需要在列表的后半部分匹配该偏移量。一个更简单的方法是观察，在这相当于匹配相同的索引，但从列表的末尾开始。给定当前day偏移量(day + (numDays - idx)) % numDays。

UPDATE 3:I was not happy that my solution involved such convoluted selection, matching, reversing of array elements. After I got thinking about what my solution involved I realized that I was too hung up about keep the order of the teams as given. However, that is not a requirement and one can get a different but equally valid schedule by not caring about the initial ordering. All that matters is the selection algorithm I describe in the second part of my explanation.

更新 3：我对我的解决方案涉及如此复杂的数组元素选择、匹配和反转感到不高兴。在我考虑了我的解决方案所涉及的内容后，我意识到我对保持团队的秩序太犹豫了。但是，这不是必需的，您可以通过不关心初始排序来获得不同但同样有效的时间表。重要的是我在解释的第二部分中描述的选择算法。

Thus you can simplify the following lines:

因此，您可以简化以下几行：

teams.AddRange(ListTeam.Skip(halfSize).Take(halfSize));
teams.AddRange(ListTeam.Skip(1).Take(halfSize -1).ToArray().Reverse());

to:

到：

teams.AddRange(ListTeam); // Copy all the elements.
teams.RemoveAt(0); // To exclude the first team.

回答by bmm6o

It sounds like you want to schedule a round-robin tournament. The wp article contains the algorithm.

听起来您想安排循环赛。wp文章包含算法。

I don't see where you are even trying to rotate the array. The permutation will look something like: 1 -> 2 -> 3 -> 4 ... -> n/2 - 1 -> n - 1 -> n - 2 -> n - 3 -> ... -> n/2 -> 1 (and 0 stays fixed). You can do that in 2 loops (top row and bottom row).

我什至看不到您试图旋转阵列的位置。排列看起来像：1 -> 2 -> 3 -> 4 ... -> n/2 - 1 -> n - 1 -> n - 2 -> n - 3 -> ... -> n /2 -> 1（并且 0 保持不变）。您可以在 2 个循环中执行此操作（顶行和底行）。

回答by RobS

How about calculating the possible combinations for each day that you want then

那么如何计算您想要的每一天的可能组合

1. sort them within each pair i.e. lowest number team is always first in any pair.
2. sort the listed pairings for each day by the first in each pair.

1. 在每对中对它们进行排序，即最低数量的团队总是在任何一对中排在第一位。
2. 按每对中的第一个对每天列出的配对进行排序。

回答by tw39124

It may be a convoluted method, but this can be reduced to a graph theory problem. Create a graph vertex for each team, and create an edge between every vertex (so it is a complete graph). Then for the algorithm:

这可能是一种复杂的方法，但这可以简化为图论问题。为每个团队创建一个图顶点，并在每个顶点之间创建一条边（所以它是一个完整的图）。然后对于算法：

For each day i = 1 .. n :

对于每一天 i = 1 .. n ：

• Pick any two unmarked vertices that are directly connected and label the edge between them with i. Mark both vertices.
• Repeat until all vertices are marked.
• Output the labelled edges (i.e. team1 vs team2, team3 vs team4 etc)
• Delete the labelled edges from the graph and reset all vertices to unmarked.

• 选取任意两个直接相连的未标记顶点，并用 i 标记它们之间的边。标记两个顶点。
• 重复直到所有顶点都被标记。
• 输出标记的边（即 team1 vs team2, team3 vs team4 等）
• 从图中删除标记的边并将所有顶点重置为未标记。

回答by Adonis07

I made some improvements in the answered code block that calculates double round-robin schedule

我对计算双循环调度的回答代码块做了一些改进

GameEntities db = new GameEntities();


private void btnTeamFixtures_Click(object sender, RoutedEventArgs e)
    {
        txtResults.Text = null;

        var allTeams = db.Team.Select(t => t.TeamName);

        int numDays = allTeams.Count() - 1;
        int halfsize = allTeams.Count() / 2;

        List<string> temp = new List<string>();
        List<string> teams = new List<string>();

        teams.AddRange(allTeams);
        temp.AddRange(allTeams);
        teams.RemoveAt(0);

        int teamSize = teams.Count;

        for (int day = 0; day < numDays * 2; day++)
        {
            //Calculate1stRound(day);
            if (day % 2 == 0)
            {
                txtResults.Text += String.Format("\n\nDay {0}\n", (day + 1));

                int teamIdx = day % teamSize;

                txtResults.Text += String.Format("{0} vs {1}\n", teams[teamIdx], temp[0]);

                for (int idx = 0; idx < halfsize; idx++)
                {
                    int firstTeam = (day + idx) % teamSize;
                    int secondTeam = ((day + teamSize) - idx) % teamSize;

                    if (firstTeam != secondTeam)
                    {
                        txtResults.Text += String.Format("{0} vs {1}\n", teams[firstTeam], teams[secondTeam]);
                    }
                }
            }

            //Calculate2ndRound(day);
            if (day % 2 != 0)
            {
                int teamIdx = day % teamSize;

                txtResults.Text += String.Format("\n\nDay {0}\n", (day + 1));

                txtResults.Text += String.Format("{0} vs {1}\n", temp[0], teams[teamIdx]);

                for (int idx = 0; idx < halfsize; idx++)
                {
                    int firstTeam = (day + idx) % teamSize;
                    int secondTeam = ((day + teamSize) - idx) % teamSize;

                    if (firstTeam != secondTeam)
                    {
                        txtResults.Text += String.Format("{0} vs {1}\n", teams[secondTeam], teams[firstTeam]);
                    }
                }
            }
        }
    }

If u want u can create 2 methods and pass and integer(Day) like i did in the 2 commented lines, to separate the code.

如果你想要你可以创建 2 个方法并传递和 integer(Day) 就像我在 2 条注释行中所做的那样，以分隔代码。

If you have any questions or suggestions feel free to reply.

如果您有任何问题或建议，请随时回复。

回答by PerlDev

Assuming we always have even number teams/players (if odd, add BYE; for my case the teams/players ranked by their rating, we would like to have the top seeded team/player to play weaker opponent first), Here is my implementation.

假设我们总是有偶数球队/球员（如果是奇数，加上 BYE；对于我的情况，球队/球员按他们的等级排名，我们希望头号种子球队/球员首先与较弱的对手比赛），这是我的实现.

void CreateSchedule(int n)
{
    int[] orig = new int[n];
    for(int i=0;i<n; i++){
        orig[i] = i + 1;
    }   
    IEnumerable<int> rev = orig.Reverse();

    int len = orig.Length;
    for (int j = 0; j < len - 1; j++)
    {
        List<int> tmp = new List<int>();
        tmp.Add(orig[0]);
        tmp.AddRange(rev.Take(j).Reverse());
        if (j < len && len > 1 + j) tmp.AddRange(orig.Skip(1).Take(len - 1 - j));
        PrintMe(tmp, j + 1);
    }
}

void PrintMe(IEnumerable<int> arr, int round)
{

    Console.WriteLine("----------Round {0}----------------", round);
    int halfSize = arr.Count() / 2;

    IEnumerable<int> A = arr.Take(halfSize);
    IEnumerable<int> B = arr.Skip(halfSize).Take(halfSize).Reverse();

    var Result = A.Zip(B, (x, y) => $"{x} vs {y}");
    Console.WriteLin(Result);
}

回答by Nikolay Kostov

Based on the @paracycle's answer, I am providing a better code with the following changes:

根据@paracycle 的回答，我提供了一个更好的代码，并进行了以下更改：

• My method is based on the generic type T
• My code doesn't change the original teamslist innstance
• Improved code quality

• 我的方法是基于泛型类型 T
• 我的代码不会更改原始teams列表实例
• 提高代码质量

public static IEnumerable<(int Day, T First, T Second)> ListMatches<T>(IList<T> teams)
{
    var matches = new List<(int, T, T)>();
    if (teams == null || teams.Count < 2)
    {
        return matches;
    }

    var restTeams = new List<T>(teams.Skip(1));
    var teamsCount = teams.Count;
    if (teams.Count % 2 != 0)
    {
        restTeams.Add(default);
        teamsCount++;
    }

    for (var day = 0; day < teamsCount - 1; day++)
    {
        if (restTeams[day % restTeams.Count]?.Equals(default) == false)
        {
            matches.Add((day, teams[0], restTeams[day % restTeams.Count]));
        }

        for (var index = 1; index < teamsCount / 2; index++)
        {
            var firstTeam = restTeams[(day + index) % restTeams.Count];
            var secondTeam = restTeams[(day + restTeams.Count - index) % restTeams.Count];
            if (firstTeam?.Equals(default) == false && secondTeam?.Equals(default) == false)
            {
                matches.Add((day, firstTeam, secondTeam));
            }
        }
    }

    return matches;
}

Code to test it:

测试它的代码：

foreach (var match in ListMatches(new List<string> { "T1", "T2", "T3", "T4", "T5", "T6" }))
{
    Console.WriteLine($"{match.Day} => {match.First}-{match.Second}");
}

Output for 6 teams:

6支球队的输出：

0 => T1-T2
0 => T3-T6
0 => T4-T5
1 => T1-T3
1 => T4-T2
1 => T5-T6
2 => T1-T4
2 => T5-T3
2 => T6-T2
3 => T1-T5
3 => T6-T4
3 => T2-T3
4 => T1-T6
4 => T2-T5
4 => T3-T4

Output for 5 teams:

5支球队的输出：

0 => T1-T2
0 => T4-T5
1 => T1-T3
1 => T4-T2
2 => T1-T4
2 => T5-T3
3 => T1-T5
3 => T2-T3
4 => T2-T5
4 => T3-T4

回答by Vlad Nan

I've posted my implementation on github RoundRobinTournamentScheduleYou can find corresponding nuget package and use it in your own solution

我已经在 github RoundRobinTournamentSchedule上发布了我的实现 你可以找到相应的 nuget 包并在你自己的解决方案中使用它

Cheers

干杯