分发火柴 'tournament friendly'

Question

假设我有四支队伍，ABCD，我想创建比赛，让每支队伍平分秋色：

不需要

甲对乙
A 对 C
A 对 D
乙对丙
乙对丁
C 对 D

需要

甲对乙
C 对 D
乙对丙
A 对 D
A 对 C
乙对丁

换一种说法：我希望球队连续比赛的次数尽可能少。
目标语言是 C#，但我可以轻松翻译。

编辑：快速旁注，可以超过 4 个团队！

Answer 1

我想你可以通过以下方式实现你需要做的事情。如果您有 n 支球队，则球队之间所有可能的比赛都可以用 Kn Complete graph.

表示

我想出你想要的排序的方法是从该图中获取（删除）边，一次一个，总是试图找到与之前不匹配的团队匹配的边。此外，我认为这种方法（有一点变化）可以用来产生最大化并发比赛的最佳方式，如果每次你占据优势，你都选择了最长时间没有比赛的球队。

为简单起见，假设团队是 0 到 n-1 范围内的整数。该图可以简单地用布尔矩阵表示。要选择与最长时间未参加比赛的球队进行比赛，您可以跟踪每支球队上次比赛的时间。对于 n 支球队，您总共有 n*(n-1)/2 场比赛。

IEnumerable<Tuple<int,int>> GenerateMatches(int n) {
    bool[,] pendingMatches = new bool[n,n];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++)
            pendingMatches[i,j] = true;
    }

    int[] lastPlayed = new int[n];
    int totalMatches = n*(n-1)/2;
    for (int m = 1; m <= totalMatches; m++) {
        Tuple<int, int> t = null;
        int longestPlayed = -1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (pendingMatches[i,j]) {
                    int moreRecentlyPlayed = Math.Max(lastPlayed[i], lastPlayed[j]);
                    int timeSinceLastPlay = m - moreRecentlyPlayed;
                    if (timeSinceLastPlay > longestPlayed) {
                        longestPlayed = timeSinceLastPlay;
                        t = Tuple.Create(i,j);
                    }
                }
            }
        }
        lastPlayed[t.Item1] = lastPlayed[t.Item2] = m;
        pendingMatches[t.Item1, t.Item2] = false;
        yield return t;
    }
}

选择下一场比赛的部分是嵌套最多的两个for。如果您使用某种优先级队列来调整涉及更新 lastPlayed 数组后最后选择的边的团队的边的优先级，则可以提高该部分的复杂性。

希望对您有所帮助。

Answer 2

解决此问题的一种方法是执行以下步骤：

创建一个包含匹配组合总数的集合。
创建一个与第 1 步中的集合长度相同的新集合。
遍历第1步中的项目，在第2步中添加相同的项目，条件是下一个要添加的项目与上次添加的项目之间的最大差异。

一些示例代码：

// Just a container to conveniently hold a match between two teams
public class Match
{
    public Match(string teamOne, string teamTwo)
    {
        TeamOne = teamOne;
        TeamTwo = teamTwo;
    }

    public string TeamOne { get; private set; }

    public string TeamTwo { get; private set; }

    public override string ToString()
    {
        return String.Format("{0} vs {1}", TeamOne, TeamTwo);
    }
}

public class MatchMaking
{
    public MatchMaking()
    {
        Teams = new List<string> { "A", "B", "C", "D", "E" };
    }

    public IList<string> Teams { get; private set; }

    public IList<Match> GetMatches()
    {
        var unorderedMatches = GetUnorderedMatches();

        // The list that we will eventually return
        var orderedMatches = new List<Match>();

        // Track the most recently added match
        Match lastAdded = null;

        // Loop through the unordered matches
        // Add items to the ordered matches
        // Add the one that is most different from the last added match
        for (var i = 0; i < unorderedMatches.Count; i++)
        {
            if (lastAdded == null)
            {
                lastAdded = unorderedMatches[i];
                orderedMatches.Add(unorderedMatches[i]);
                unorderedMatches[i] = null;
                continue;
            }

            var remainingMatches = unorderedMatches.Where(m => m != null);

            // Get the match which is the most different from the last added match
            // We do this by examining all of the unadded matches and getting the maximum difference
            Match mostDifferentFromLastAdded = null;
            int greatestDifference = 0;
            foreach (var match in remainingMatches)
            {
                var difference = GetDifference(lastAdded, match);
                if (difference > greatestDifference)
                {
                    greatestDifference = difference;
                    mostDifferentFromLastAdded = match;
                }

                if (difference == 2)
                {
                    break;
                }
            }

            // Add the most different match
            var index = unorderedMatches.ToList().IndexOf(mostDifferentFromLastAdded);
            lastAdded = unorderedMatches[index];
            orderedMatches.Add(unorderedMatches[index]);
            unorderedMatches[index] = null;
        }

        return orderedMatches;
    }

    // Create a list containing the total match combinations with an arbitrary order
    private List<Match> GetUnorderedMatches()
    {
        var totalNumberOfCombinations = AdditionFactorial(Teams.Count - 1);

        var unorderedMatches = new List<Match>(totalNumberOfCombinations);
        for (int i = 0; i < Teams.Count; i++)
        {
            for (int j = 0; j < Teams.Count; j++)
            {
                if (j <= i) continue;

                unorderedMatches.Add(new Match(Teams[i], Teams[j]));
            }
        }
        return unorderedMatches;
    }

    // Get the difference between two matches
    // 0 - no difference, 1 - only one team different, 2 - both teams different
    private int GetDifference(Match matchOne, Match matchTwo)
    {
        var matchOneTeams = new HashSet<string> { matchOne.TeamOne, matchOne.TeamTwo };
        var matchTwoTeams = new HashSet<string> { matchTwo.TeamOne, matchTwo.TeamTwo };
        var intersection = matchOneTeams.Intersect(matchTwoTeams);

        return (intersection.Count() - 2) * -1;
    }

    // Just a helper to get the total number of match combinations
    private int AdditionFactorial(int seed)
    {
        int result = 0;

        for (int i = seed; i > 0; i--)
        {
            result += i;
        }

        return result;
    }
}

public class Program
{
    private static void Main(string[] args)
    {
        var matchMaking = new MatchMaking();

        foreach (var match in matchMaking.GetMatches())
        {
            Console.WriteLine(match);
        }
    }
}

分发火柴 'tournament friendly'

Distribute matches 'tournament friendly'

c#

distribution

evenly

matchmaking