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

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