Creating a tournament schedule

Hello everyone,

I am working on a small problem for which I would like to create a tournament schedule with the following requirements:

• There are 10 teams, each team participates in an activity every round
• There are five rounds and five activities, each round 2 teams compete in each activity
• Each team has to participate in each activity once
• Each team can only play another team once

With these requirements in mind, to me it sounds a bit like a Sudoku, so I downloaded a Sudoku solver and adjusted it, such that it holds for 5 rows and 5 columns. Each column and each row can only contain the numbers 1 through 5 once. The Sudoku solver gives me plenty of solutions of which I can choose 2 (the second solution I simply replace the numbers 1 through 5 with 6 through 10) such that each team participates in each activity and competes with another team in these activities. An example:

S1=      
   1     2     3     4     5
   2     1     4     5     3
   3     4     5     2     1
   4     5     1     3     2
   5     3     2     1     4
S2=
   1     2     3     4     5
   2     1     4     5     3
   3     5     2     1     4
   4     3     5     2     1
   5     4     1     3     2

In this example, each row is a round and each column is an activity. As you can see, in the first round, team 1 plays against team 6 (replace the 1 with a 6 in S2) in the first activity, and in the second round, team 1 participates in activity 2, but again against team 6. How can I make sure that the program gives me 2 matrices in which no team plays another team more than once?

Two ideas:

• Is it possible to make a 3D matrix (5 rounds, 5 activities and 2 teams per activity/round) and solve with the numbers 1 through 10, instead of making 2 matrices with twice 1 through 5? This also gives the possibility for team 1 playing against team 2 which allows for more options (but I do not know how to implement this)
• Could I use the function find here and if so, how can I define what I am looking for?

Thanks for your help!

Answer 1

[John D'Errico]

This is just a round robin of a sort. Can I solve it using a greedy strategy?

Start out by list all possible combinations.

P = perms(1:10)';
P = reshape(P,2,5,[]);

Next, I really don't care what order each pair visits any activity. So 9 and 10 are the same event as 10 and 9.

P = sort(P,1);

There are factorial(10) possible permutations in this list. On the first round, we can arbitrarily choose this pairing:

P(:,:,1)
ans =
     9     7     5     3     1
    10     8     6     4     2

So 9 and10 are on activity 1, etc., with column indicating the activity. I'll store all 5 rounds in a 2x5x5 array.

rounds = zeros(2,5,5);
rounds(:,:,1) = P(:,:,1)

rounds(:,:,1) =
     9     7     5     3     1
    10     8     6     4     2
rounds(:,:,2) =
     0     0     0     0     0
     0     0     0     0     0
rounds(:,:,3) =
     0     0     0     0     0
     0     0     0     0     0
rounds(:,:,4) =
     0     0     0     0     0
     0     0     0     0     0
rounds(:,:,5) =
     0     0     0     0     0
     0     0     0     0     0

For all future rounds, we wish to never see 9 or 10 in activity 1, 7 or 8 in activity 2, etc.

exclude = find((any(any(rounds(1,:,1) == P,1),2)) | (any(any(rounds(2,:,1) == P,1),2)));
P(:,:,exclude) = [];

There are now

size(P)
ans =
           2           5      440192

So 440192 possible pairings that remain. So of all 3628800 original possible pairings, merely requiring that 1 and 2 NEVER visit activity 5 again, etc., we have reduced the possible remaining pairings by a factor of 9.

P(:,:,1)
ans =
     7     9     3     1     5
     8    10     4     2     6

As you see though, the first such pairing in the list was also illegal, since 1 must never pair with 2 again. As well, 3 and 4, 9 and 10, 7 and 8, 5 and 6 are all invalid pairs. So we need to exclude more possible cases.

exclude = any(all(rounds(:,:,1) == P,1),2);
for i = 1:4
  exclude = exclude | any(all(circshift(rounds(:,:,1),i,2) == P,1),2);
end
P(:,:,exclude) = [];

So simply by excluding all possible second rounds from consideration, there are now only 221184 possible second round pairings.

size(P)
ans =
           2           5      221184

Arbitrarily, one of them is:

P(:,:,1)
ans =
     6     5     2     1     3
     8    10     4     9     7

rounds(:,:,2) = P(:,:,1);

Now, can we reduce the set of possible pairings that remain a second time?

exclude = find((any(any(rounds(1,:,2) == P,1),2)) | (any(any(rounds(2,:,2) == P,1),2)));
P(:,:,exclude) = [];
exclude = any(all(rounds(:,:,2) == P,1),2);
for i = 1:4
  exclude = exclude | any(all(circshift(rounds(:,:,2),i,2) == P,1),2);
end
P(:,:,exclude) = [];

size(P)
ans =
           2           5        7552

Hmm. After two rounds, there are only 7552 possible third round pairings. Pick one of them, and save it as the third round.

rounds(:,:,3) = P(:,:,1)
rounds(:,:,1) =
     9     7     5     3     1
    10     8     6     4     2
rounds(:,:,2) =
     6     5     2     1     3
     8    10     4     9     7
rounds(:,:,3) =
     5     6     1     2     4
     7     9     3    10     8
rounds(:,:,4) =
     0     0     0     0     0
     0     0     0     0     0
rounds(:,:,5) =
     0     0     0     0     0
     0     0     0     0     0

Repeat to choose a 4th round pairing. There are only 128 that remain. Choose one arbitrarily.

size(P)
ans =
     2     5   128

rounds(:,:,4) = P(:,:,1)
rounds(:,:,1) =
     9     7     5     3     1
    10     8     6     4     2
rounds(:,:,2) =
     6     5     2     1     3
     8    10     4     9     7
rounds(:,:,3) =
     5     6     1     2     4
     7     9     3    10     8
rounds(:,:,4) =
     1     2     8     6     5
     4     3    10     7     9
rounds(:,:,5) =
     0     0     0     0     0
     0     0     0     0     0

How many pairings remain?

P
P =
  2×5×0 empty double array

Sadly zero pairings remain for the 5th round. I have a funny feeling that there is no such round robin over only 5 activities for 10 contestants with 5 full rounds. Admittedly, I used a greedy strategy, by choosing one arbitrary pairing each round.

[Roos Bulthuis]

Thank you so much for your help. Funny, I never considered the possibility that it would not be possible at all! I have a small problem with running your code though. This line:

exclude = find((any(any(rounds(1,:,1) == P,1),2)) | (any(any(rounds(2,:,1) == P,1),2)));

Gives me the following error:

Error using  == Number of array dimensions must match for binary array op.

I am a bit of a Matlab newby, so I cannot really figure out what the problem is, I assume there is some typo that I overlook?

If you look at it from a distance, could the problem be solved only if you add more teams? Or maybe would it be possible if we add a 6th round and each round 2 teams have a 'break' and it does not matter if these two teams have already played each other (or will do after the break) during one of the activities? So basically:

• Each round, there is one activity without teams (can also be the 'break')
• Each round there are 2 teams that have a break and it does not matter if they have played each other or will do

Or do you think we simply need more teams? Anyways, I hope you also find it a fun problem to think about for a bit longer, since I am not capable of coming up with an answer myself!

Answer 2

[Ashwin Vaidyanathan]

Hi,

There actually exists a solution for your question, but this solution can be achieved only if a particular pattern of scheduling is followed. Let me explain that pattern first. It might be a little long and winding, but please bear with me.

For convenience, let's divide the 10 teams into two sets of 5 teams each (Set A and Set B). Each team from Set A will play every team in Set B exactly once and vice versa. For starters, let's consider only the teams from Set A.

Set_A = [1 2 3 4 5]; Set_B = [6 7 8 9 10]

There is a constraint that every team must participate in every activity exactly once over the course of the five rounds. This implies that, if each activity is represented by a position or index of an array, every team must occupy each position of the array exactly once over the course of the five rounds. For this to be feasible, every team must traverse the positions of the array according to some specific rule from one round to another. Assume the teams in Set A follow Rule X to traverse the positions of the array. I'll get to that rule a little later in the piece.

Fix_Set_A = [1 2 3 4 5;
             5 1 2 3 4;
             4 5 1 2 3;
             3 4 5 1 2;
             2 3 4 5 1]; % Set A Teams assigned to different activities in each round using Rule X

Now, consider what happens if the teams in Set B also follow the same rule (Rule X) to traverse the positions of the activity array from one round to another. We'll have the same set of matchups in every round, with each matchup assigned to a different activity in each round. To avoid this scenario, the teams in Set B must traverse the positions of the activity array according to a rule that is different from Rule X. Let this new rule be Rule Y.

% If Rule X is same as Rule Y
Fix (:,:,1) =

    1   2   3   4   5
    6   7   8	9  10 % Round 1


Fix (:,:,2) =

    5   1   2   3   4
    10	6   7   8   9 % Round 2 - Different activities but same matchups as Round 1

Now what exactly is this 'rule'? It is basically a function or mapping that systematically shifts or relocates the elements of an array after every round. For instance, the Rule X mentioned above may be defined as a function that shifts every element of Set A by 1 position to the right after every round. (Note that overlapping is allowed (i.e.) shifting the element in the last position by one position to the right brings it to the first position.) In MATLAB, the rule may defined using the mod function. In a similar vein, Rule Y can be defined such that it shifts every element of Set B by 2 positions to the right after every round.

At this stage, one may wonder whether the magnitude of the shift produced by each rule can be arbitrarily defined. The answer is a definitive 'no'. To ensure feasible scheduling, the magnitude of the shift and the number of activities must be "co-prime". Otherwise, in later rounds, the rule may incorrectly allocate a team to an activity that it has already participated in. Here, for your problem, it can be easily verified that both Rule X and Rule Y shift the elements in a feasible manner, as the respective magnitudes of shift (1 and 2) and the number of activities (5) are co-prime.

But there is another catch here: The individual matchups must not be repeated. To ensure this, it is necessary to understand how the elements of one set shift relative to those of the other set. Rule X shifts every element of A by 1 position to the right, while Rule Y shifts every element of B by 2 positions to the right, after every round. The relative shift of elements of B over those of A is therefore 1 position to the right. Note that, if the relative shift is zero, the same matchups are repeated in every round. Also, if the relative shift and the no. of activities are not co-prime, the same matchups may be repeated after a few rounds.

Thus, a feasible schedule can be obtained for your problem only when the following 3 conditions are satisfied:

• Shift of Rule X and the no. of activities must be co-prime
• Shift of Rule Y and the no. of activities must be co-prime
• Relative Shift of Rule Y over Rule X and the no. of activities must be co-prime

The given problem can be generalized as an n-rounds, n-activities, 2n-teams problem. A little consideration shows that whenever n is even, there can be no feasible solution to the problem. So, such problems can only be defined for odd values of n greater than 1. As your problem takes n=5, it is perfectly solvable.

I'm also embedding the code for the same. Hope it helps.

Cheers.

n=5; % No. of activities (or) No. of rounds
Set_A=randperm(n); %Set A initialized with teams 1 to 5 in random order
Set_B=n+randperm(n);%Set B initialized with teams 6 to 10 in random order
X_Shift=1; % No.of positions by which every element in Set A is shifted to the right after every round
Y_Shift=2; % No.of positions by which every element in Set B is shifted to the right after every round
fix=zeros(2,n,n); % 3-D array for holding the matchups round wise. The last dimension represents the round
fix(1,:,1)=Set_A; % Assigning Set A teams to activities for the first round
fix(2,:,1)=Set_B; % Assigning Set B teams to activities for the first round
for i=2:n % For each round
    for j=1:n % For each activity
        fix(1,mod(j+X_Shift-1,n)+1,i)=fix(1,j,i-1); % Shifting the Set A teams to different activities for next round
        fix(2,mod(j+Y_Shift-1,n)+1,i)=fix(2,j,i-1); % Shifting the Set B teams to different activities for next round
    end
end

The round-wise schedule output is as follows:

fix(:,:,1) =

     5     4     1     3     2
    10     8     6     9     7


fix(:,:,2) =

     2     5     4     1     3
     9     7    10     8     6


fix(:,:,3) =

     3     2     5     4     1
     8     6     9     7    10


fix(:,:,4) =

     1     3     2     5     4
     7    10     8     6     9


fix(:,:,5) =

     4     1     3     2     5
     6     9     7    10     8

Note: Additionally, you can shuffle the rows in pairs, if needed, to make the fixtures look slightly more randomized. Also, you can change the X-Shift and Y-Shift values without violating the conditions specified to achieve the same effect. You can even take negative values for the shifts, but ensure that only their absolute values are taken while evaluating the specified conditions.

[Krystian]

Unfortunately teams cannot play within their own Sets

[Ashwin Vaidyanathan]

The original poster did not specify that every team has to play every other team (which certainly isn't possible given that there are 10 teams and only 5 rounds). The constraints only state that every team must participate in every activity exactly once and no team should play any other team more than once. The given solution satisfies the constraints put forth by the original poster.