For one project, I need to compute matchs planning between several teams. Requirement: I've a pair number of teams All teams have to play against every other team once(and only once) All team plays at the same time E.g. With 4teams(A,B, C and D), I would like to be able to compute this: Round 1 A vs B C vs D Round 2 A vs D B vs C Round 3 A vs C B vs D The problem is that, there is some choice in round X which will make impossible any match in round X+1(teams have already played against other teams). I think I can use some backtracking technique, but I'm searching if there is an algorithm for this? This will be implemented in c#. Have you any idea about how to do this?

c#algorithmmatchmatching

J4N

Reputation: 20717

"Match making" algorithm?

For one project, I need to compute matchs planning between several teams.

Requirement:

I've a pair number of teams
All teams have to play against every other team once(and only once)
All team plays at the same time

E.g. With 4teams(A,B, C and D), I would like to be able to compute this:

Round 1

A vs B
C vs D

Round 2

A vs D
B vs C

Round 3

A vs C
B vs D

The problem is that, there is some choice in round X which will make impossible any match in round X+1(teams have already played against other teams).

I think I can use some backtracking technique, but I'm searching if there is an algorithm for this?

This will be implemented in c#.

Have you any idea about how to do this?

Upvotes: 3

Answers (4)

zeFrenchy

Reputation: 6591

My quick go at it, using no-brainer method

generate all possible games
allocate games to rounds based on team availabibity

This result in a distribution of games which seem a little "stiff".

schedule_tournament(new List<string> { "A", "B", "C" });
schedule_tournament(new List<string> { "A", "B", "C", "D", });
schedule_tournament(new List<string> { "A", "B", "C", "D", "E" });
schedule_tournament(new List<string> { "A", "B", "C", "D", "E", "F" });
schedule_tournament(new List<string> { "A", "B", "C", "D", "E", "F", "G" });
...

private void schedule_tournament(List<string> teams)
{            
    List<string> games = new List<string>();
    List<string> rounds = new List<string>();

    // get all possible games
    for (int i = 0; i < teams.Count; i++)
    {
        for (int j = i + 1; j < teams.Count; j++)
        {
            string game_name = string.Format("{0}{1}", teams[i], teams[j]);
            if (!games.Contains(game_name)) games.Add(game_name);
        }
    }

    // allocate games to rounds
    for (int i = 0; i < games.Count; i++)
    {
        bool allocated = false;
        for (int j = 0; j < rounds.Count; j++)
        {
            string team_1 = games[i].Substring(0, 1);
            string team_2 = games[i].Substring(1, 1);
            if (!rounds[j].Contains(team_1) && !rounds[j].Contains(team_2))
            {
                rounds[j] += " - " + games[i];
                allocated = true;
                break;
            }
        }
        if (!allocated)
        {
            rounds.Add(games[i]);
        }
    }
    Console.WriteLine("{0} teams, play {1} games in {2} rounds", teams.Count, games.Count, rounds.Count);
    for (int i = 0; i < rounds.Count; i++) Console.WriteLine("Round {0}: {1}", i + 1, rounds[i]);
}

the output of this is:

3 teams, play 3 games in 3 rounds
Round 1: AB
Round 2: AC
Round 3: BC
4 teams, play 6 games in 3 rounds
Round 1: AB - CD
Round 2: AC - BD
Round 3: AD - BC
5 teams, play 10 games in 7 rounds
Round 1: AB - CD
Round 2: AC - BD
Round 3: AD - BC
Round 4: AE
Round 5: BE
Round 6: CE
Round 7: DE
6 teams, play 15 games in 7 rounds
Round 1: AB - CD - EF
Round 2: AC - BD
Round 3: AD - BC
Round 4: AE - BF
Round 5: AF - BE
Round 6: CE - DF
Round 7: CF - DE
7 teams, play 21 games in 7 rounds
Round 1: AB - CD - EF
Round 2: AC - BD - EG
Round 3: AD - BC - FG
Round 4: AE - BF - CG
Round 5: AF - BE - DG
Round 6: AG - CE - DF
Round 7: BG - CF - DE

Upvotes: 0

user1597825

Reputation:

Try round-robin. This is a simple scheduling algorithm to share timeslots among processes, but this problem reminds me it somehow.

EDIT

Now here is an implementation of Round-robin tournament. If we have ODD number of teams, we must insert a dummy team, otherwise there would be a team without opponent. As number of rounds are EVEN, number of total rounds are (NumberOfTeams-1). At the very beginning we set-up the first round:

A B C D E F G H

H G F E D C B A

So, Team A - H, Team B - G, etc.

From now, we keep one team fixed, for instance A. Then we shift A_Side teams from the 2nd position to the right. The last team will come into position 2. ( A B C D E F G H will be A H B C D E F G). See rotate_A_side() recursive method (just for fun).

The half of the B_Sides are shifted left. This will make H G F E D - G F E D.

As team selection is symmetric (A plays with H, then H plays wiht A), the upper half of B_Side is the reverse copy of the A_Side low part teams. So, D C B A will be C B H A). See rotate_B_side().

So, Round 2 is:

A H B C D E F G

G F E D C B H A

To give all rounds, simply repeat the aforementioned shifting steps. See NextRound()

Here is a c# class which implements the algorithm:

    class Teams
{
    private int[] A_Side;
    private int[] B_Side;
    public int[,] PlayingCounter;
    public int RoundCounter = 1;
    public bool DummyTeam = false;                 // ODD number of teams -> one team will no be able to play.

    public bool NextRoundExists
    {
        get
        {
            return (RoundCounter < B_Side.Length-1);

        }
    }
    public Teams(int NumberOfTeams)
    {
        if (NumberOfTeams % 2 != 0)
        {
            NumberOfTeams++; DummyTeam = true;
        }
        A_Side = new int[NumberOfTeams];
        B_Side = new int[NumberOfTeams];
        PlayingCounter = new int[NumberOfTeams,NumberOfTeams];     // Counting to see if alg is correct
        int x,y;
        for (x=0; x<NumberOfTeams; x++) 
        {
            A_Side[x] = x + 1;                  
            B_Side[NumberOfTeams-x-1]=x+1; 
            for (y=0;y<NumberOfTeams;y++) 
            {
                PlayingCounter[x,y] = 0;
            }

        }

    }

    private void rotate_A_Side(int AtPos)
    {
        if (AtPos == 1)
        {
            int iO = A_Side[A_Side.Length - 1];
            rotate_A_Side(AtPos+1);
            A_Side[1] = iO;
        }
        else 
        {
            if (AtPos < A_Side.Length - 1) { rotate_A_Side(AtPos + 1); }
            A_Side[AtPos] = A_Side[AtPos - 1];
        }
    }
    public void rotate_B_Side()
    {
        int i;
        for (i = 0; i<B_Side.Length/2 ; i++)
        {
            B_Side[i] = B_Side[i + 1];
        }
        for (i = B_Side.Length / 2; i < B_Side.Length; i++)
        {
            B_Side[i] = A_Side[B_Side.Length/2 - (i -B_Side.Length/2 + 1) ];
        }

    }
    public bool NextRound()
    {
        if (NextRoundExists)
        {
            RoundCounter++;         // Next round
            rotate_A_Side(1);       // A side rotation
            rotate_B_Side();        // B side rotation
            LogRound();             // Update counters
            return true;
        }
        else return false;
    }
    public void LogRound()
    {
        for (int x = 0; x < A_Side.Length; x++)
        {
            PlayingCounter[A_Side[x]-1, B_Side[x]-1]++;
            PlayingCounter[B_Side[x]-1, A_Side[x]-1]++;
        }
    }
    public string GetCounters()
    {
        string return_value = "";

        for (int y = 0; y < A_Side.Length; y++)
        {
            for (int x = 0; x < A_Side.Length; x++)
            {
                return_value += String.Format(" {0:D3}", PlayingCounter[y, x]);
            }
            return_value += System.Environment.NewLine;
        }
        return return_value;
    }

    public string GetCurrentRound()
    {
        string Round = "Round #" + RoundCounter.ToString() + " ";
        for (int x = 0; x < B_Side.Length; x++)
        {
            Round += String.Format("Team {0} - Team {1};", A_Side[x], B_Side[x]);
        }
        return Round;
    }

}

From your code, you can use it like:

Teams Rounds = new Teams(22);
if (Rounds.DummyTeam) { 
       // Anything to do if nober of teams is odd?
}
Rounds.LogRound();    // DEBUG - you can check number of matches ;-)
while (Rounds.NextRoundExists)     // While we have next round...
 {
   Rounds.NextRound();             // ... generate the next 
                                   //     round (team assignment)
   // Your can tack using: Rounds.GetCurrentRound()
 }
// If you want to see the number of matches, call Rounds.GetCounters();

6 Teams gave me the following output:

Round #1 A-F ; B-E ; C-D ; D-C ; E-B ; F-A ;

Round #2 A-E ; F-D ; B-C ; C-B ; D-F ; E-A ;

Round #3 A-D ; E-C ; F-B ; B-F ; C-E ; D-A ;

Round #4 A-C ; D-B ; E-F ; F-E ; B-D ; C-A ;

Round #5 A-B ; C-F ; D-E ; E-D ; F-C ; B-A ;

I replaced Team 1 with A, etc.

rotate_B_Side() should be refined, this is a quick approach.

Upvotes: 1

Cristian Lupascu

Reputation: 40526

Actually the answer is in the link Olivier provided in the comments. More specifically, this answer.

And it does handle the notion of Round, except it's not very obvious. In that code a Tuple<string, string> represents a match (an item containing two team names) and a List<Tuple<string, string>> represents a round (collection of Matches).

The code returns a collection of Rounds in the form of a List<List<Tuple<string, string>>>.

I refactored the code a bit so that the notions of Match and Round would be more obvious in the code.

Here are the Match and Round classes:

public class Match
{
    public string Team1 { get; set; }
    public string Team2 { get; set; }

    public Match(string team1, string team2)
    {
        Team1 = team1;
        Team2 = team2;
    }

    public override string ToString()
    {
        return string.Format("{0} vs {1}", Team1, Team2);
    }
}

public class Round
{
    public List<Match> Matches { get; private set; }

    public Round()
    {
        Matches = new List<Match>();
    }

    public override string ToString()
    {
        return String.Join(Environment.NewLine, Matches) + Environment.NewLine;
    }
}

And here is the code that does the magic (credits go to Nagg):

public static List<Round> ComputeFixtures(List<string> listTeam)
{
    var result = new List<Round>();

    var numberOfRounds = (listTeam.Count - 1);
    var numberOfMatchesInARound = listTeam.Count / 2;

    var teams = new List<string>();

    teams.AddRange(listTeam.Skip(numberOfMatchesInARound).Take(numberOfMatchesInARound));
    teams.AddRange(listTeam.Skip(1).Take(numberOfMatchesInARound - 1).ToArray().Reverse());

    var numberOfTeams = teams.Count;

    for (var roundNumber = 0; roundNumber < numberOfRounds; roundNumber++)
    {
        var round = new Round();
        var teamIdx = roundNumber % numberOfTeams;

        round.Matches.Add(new Match(teams[teamIdx], listTeam[0]));

        for (var idx = 1; idx < numberOfMatchesInARound; idx++)
        {
            var firstTeamIndex = (roundNumber + idx) % numberOfTeams;
            var secondTeamIndex = (roundNumber + numberOfTeams - idx) % numberOfTeams;

            round.Matches.Add(new Match(teams[firstTeamIndex], teams[secondTeamIndex]));
        }

        result.Add(round);
    }

    return result;
}

Here are some online running samples for this code:

for four teams: http://ideone.com/bTfld
for six teams: http://ideone.com/fw6wE
for twelve teams: http://ideone.com/peIAI

Upvotes: 3

Samy Arous

Reputation: 6814

I think you are taking this the wrong way. Rather than computing on each round the pairing based on the previous round, I would start by making all the possible pairing using a simple double for loop, then randomly distribute the games by rounds.

Since every player will play exactly the same number of games, such distribution must exist.

Upvotes: 2

&quot;Match making&quot; algorithm?

Answers (4)

Related Questions

"Match making" algorithm?