Распределить матчи "турнир дружественных"

Question

Скажем, у меня есть четыре команды, ABCD, я хочу создавать матчи, чтобы команды делали их равномерно:

не желательно

• А против Б
• А против С
• А против Д
• B против C
• Б против Д
• С против Д

желательно

• А против Б
• С против Д
• B против C
• А против Д
• А против С
• Б против Д

Другой способ выразить это: я хочу, чтобы команды проводили матч как можно меньше подряд.
Целевой язык - C#, но я могу легко перевести.

Изменить: быстрый sidenote, это может быть более 4 команд!

Answer 1

Один из способов решить эту проблему - выполнить следующие шаги:

1. Создайте коллекцию, содержащую общее количество комбинаций совпадений.
2. Создайте новую коллекцию той же длины, что и коллекция на шаге 1.
3. Просмотрите элементы на шаге 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);
        }
    }
}

Answer 2

Я думаю, что вы можете достичь того, что вам нужно сделать, следующим образом. Если у вас n команд, все возможные совпадения между командами могут быть представлены графомKn Complete.

Способ, которым я бы придумал желаемую сортировку, состоит в том, чтобы брать (убирать) ребра из этого графика, по одному, всегда пытаясь найти ребро, которое соответствует командам, которые не соответствовали непосредственно ранее. Более того, я думаю, что этот подход (с небольшими вариациями) может быть использован для создания наилучшего способа максимизировать одновременные матчи, если каждый раз, когда вы получаете преимущество, вы выбираете тот с командами, которые не играли в большинстве случаев.

Для простоты предположим, что команды - это целые числа в диапазоне от 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;
    }
}

Часть, которая выбирает следующий матч, является двумя наиболее вложенными форами. Сложность этой части может быть улучшена, если вы используете некую очередь приоритетов, адаптированную для настройки приоритета ребер, в которые входят команды последнего выбранного ребра после обновления массива lastPlayed.

Надеюсь, это поможет.