Distribute matches 'tournament friendly'

Question

Say I have four teams, ABCD, I want to create matches so that the teams evenly have to do them:

not desired

• A vs B
• A vs C
• A vs D
• B vs C
• B vs D
• C vs D

desired

• A vs B
• C vs D
• B vs C
• A vs D
• A vs C
• B vs D

Another way of putting it: I want the teams to have a match as few in a row as possible.
Target language is C#, but I can translate easily.

Edit: Quick sidenote, it can be more than 4 teams!

Answer 1

I think you may achieve what you need doing as follows. If you've got n number of teams, all the possible matches between teams can be represented with a Kn Complete graph.

The way I would come up with your desired sorting, is taking (removing) edges from that graph, one at a time, always trying to find an edge that matches teams that didn't match immediately before. Further more, I think this approach (with a little variation) can be used to generate the best way to maximize concurrent matches, if each time you take an edge you pick the one with the teams that haven't played in most time.

For simplicity, lets assume that teams are ints in the range of 0 to n-1. The graph can simply be represented with a boolean matrix. To pick the match with the teams that haven't played in most time, you can keep track of the last time each team played. For n teams, you'll have a total of n*(n-1)/2 number of matches.

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;
    }
}

The part that chooses the next match are the two most nested fors. The complexity of that part can be improved if you use some kind of priority queue adapted to adjust the priority of edges that involve the teams of the last picked edge after updating the lastPlayed array.

Hope that helps.

Answer 2

One way to solve this is by the following steps:

1. Create a collection containing the total number of match combinations.
2. Create a new collection with the same length as the collection in step 1.
3. Go through the items in step 1, add the same item in step 2, with the condition that the next item to be added should have the maximum difference between it and the last added item.

Some sample code:

// 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);
        }
    }
}