Mathematical solution to split X teams into 3 Teams per day

Question

I am trying to split X number of Teams into "play days" which consist of 3 teams per day

There is more than one solution to solve this for 15 teams.

What is the best approach to find all possible fixtures/match plans for team count 9-21? Team count of 11, 14, 17 and 20 also cause problems, because total_matches/3="must be even/integer"

15 Teams // 105 Total Matches // 35 Total Days
D1 = 1:2  1:3  2:3
D2 = 2:4  2:5  4:5
D3 = 3:4  3:6  4:6
D4 = 4:1  4:7  1:7
D5 = 5:1  5:6  1:6
D6 = 6:2  6:7  2:7
7 = 7:3  7:5  3:5
8 = 8:1  8:9  1:9
9 = 9:2  9:10  2:10
10 = 10:1  10:11  1:11
11 = 11:2  11:8  2:8
12 = 12:1  12:13  1:13
13 = 13:2  13:14  2:14
14 = 14:1  14:15  1:15
15 = 2:12  2:15  12:15
16 = 3:8  3:10  8:10
17 = 3:9  3:11  9:11
18 = 3:12  3:14  12:14
19 = 4:8  4:12  8:12
20 = 5:8  5:13  8:13
21 = 6:8  6:14  8:14
22 = 7:8  7:15  8:15
23 = 9:4  9:13  4:13
24 = 9:5  9:12  5:12
25 = 10:4  10:14  4:14
26 = 11:4  11:15  4:15
27 = 12:6  12:10  6:10
28 = 13:3  13:15  3:15
29 = 14:5  14:11  5:11
30 = 5:10  5:15  10:15
D31 = 6:9  6:15  9:15
D32 = 6:11  6:13  11:13
D33 = 7:9  7:14  9:14
D34 = 7:10  7:13  10:13
D35 = 7:11  7:12  11:12

Answer 1

The number of possible combinations/matches of teams can mathematically be described as a Triangular Number.

For example, when there is 9 teams, the number of matches is 36.

Notice, that this number is only divisible by 3 when k or k-1 is divisible by 3. With 5 teams, you will end up with 10 possible games. Your last week will only have 1 game or you can structure it differently.

If you want to write out the combinations of matches, you can list them by iterating through the number of teams twice. Here is some example Java code. You may run it in an online Java compiler.

    public class MyClass {

        public static void main(String args[]) {
            int TEAMS = 10; //Number of teams
            int combos = 0;

            for(int i = 1; i <= TEAMS-1; i++){
                for(int j = i+1; j <= TEAMS; j++){
                    System.out.println("Team " + i + " plays Team " + j);
                    combos ++;
                }
            }

            System.out.println("There is " + combos + " possible matches");
        }
    }

We don't just want every combination of 2 teams. We want to look at combinations of 3 teams. Mathematically, we want a Combination.

We can rewrite our Triangular number as n choose k. Our previous example becomes:

Every week that we choose has 3 teams playing. The total possible day combinations is n choose 3. In our example with 9 teams.

We have 84 possible day combinations. Many of these days have overlapping games. For example, if we have teams 1, 2, and 3 play one day, then we don't want another day with teams 1,2 and 4 because then 1 and 2 play 2 games against each other. The solution for this could be to ignore duplicated games.

I want to point out that a perfect solution does not exist. For most number of teams, there is not a solution where every day 3 teams can play together that haven't already played. For example, when we have 4 teams, our games are: 1-2, 1-3, 1-4, 2-3, 2-4, 3-4. If we took 3 of those teams the first day (1-2, 1-3, 2-3) then the second day we don't get a perfect combination (1-4, 2-4, 3-4).

No matter how you break it, you can sort for the best combinations but you will end up with many random games at the end.

I created code below to look at every possible day combination and print out days that are not duplicated.

    public class MyClass {

        public static void main(String args[]) {
            int TEAMS = 9; //Number of teams

            //Keep track of each game combination used
            boolean gamesPlayed[][] = new boolean[TEAMS+1][TEAMS+1];

            int day = 1;
            for(int i = 1; i <= TEAMS-2; i++){
                for(int j = i+1; j <= TEAMS-1; j++){
                    for(int k = TEAMS; k >= j+1; k--){

                        if(!gamesPlayed[i][j] && !gamesPlayed[i][k] && !gamesPlayed[j][k] )
                        {
                            System.out.println("Day "+ day++ + " Teams " + i + ", " + j + " & " + k + " Play");
                            gamesPlayed[i][j] = true;
                            gamesPlayed[i][k] = true;
                            gamesPlayed[j][k] = true;
                        }
                    }
                }
            }


            System.out.println("\nLeftover games");
            for(int i = 1; i <= TEAMS-1; i++){
                for(int j = i+1; j <= TEAMS; j++){
                    if(! gamesPlayed[i][j])
                        System.out.println(" Team " + i + " plays Team " + j);
                }
            }



        }
    }

Answer 2

(Python) The following chooses the next three teams to group per day based on those teams that have played the least games so far and gives an ideal solution for the 9 teams case:

    from itertools import combinations
    from string import ascii_uppercase

    TEAMCOUNT = 9

    teams = ascii_uppercase[:TEAMCOUNT]     # Just use uppercase letters for teams
    # All needed 2-team games 
    games = {''.join(two_teams) for two_teams in combinations(teams, 2)}
    # All possible 3-team days and the 2-team matches they map to
    triples = {x + y + z: {x+y, x+z, y+z}
               for x, y, z in combinations(teams, 3) }

    print('Teams:', teams)
    n = 0
    while games and triples:
        # Weighting based on number of games left to play
        weight = {t: sum(t in g for g in games) for t in teams}
        to_play = {t1+t2: min([weight[t1], weight[t2]]) for t1, t2 in games}
        # Choose teams that haven't played much next
        _, chosen_triple = max((sum(to_play[m] for m in matches if m in games), 
                                day)
                               for day, matches in triples.items())
        n += 1
        print(f"  Day{n}: {chosen_triple} Games: ", 
              ' '.join(sorted(m for m in triples[chosen_triple] if m in games)))
        games -= triples[chosen_triple]  # These games are played
        del triples[chosen_triple]       # This day triple used

    if games:
        print(" After those days, the following games remain to be played:", ' '.join(sorted(games)))
    else:
        print(" All games played!")

Output for 9 Teams:

Teams: ABCDEFGHI
  Day1: GHI Games:  GH GI HI
  Day2: DEF Games:  DE DF EF
  Day3: ABC Games:  AB AC BC
  Day4: CFI Games:  CF CI FI
  Day5: BEH Games:  BE BH EH
  Day6: ADG Games:  AD AG DG
  Day7: CEG Games:  CE CG EG
  Day8: BDI Games:  BD BI DI
  Day9: AFH Games:  AF AH FH
  Day10: CDH Games:  CD CH DH
  Day11: BFG Games:  BF BG FG
  Day12: AEI Games:  AE AI EI
 All games played!