Round robin tournament scheduling using divide and conquer

Question

I want to scheduling $n$ teams using divide and conquer method for $n \in \mathbb{N}$.My approach is that if $n$ is even divide it to to group $\frac{n}{2}$ and $\frac{n}{2}$ but if $n$ is odd, add auxiliary team and scheduling $n+1$ team at the end we remove the last team and in table every match between $n+1$ team and others will mark as rest. but for some $n$ like 6 there will be a little problem. we should first schedule table for 3 team, 3 is odd so we should schedule for 4. for scheduling 4 teams we need schedule for 2 team and that's the base case so we have:

\begin{array}{c|ccc} & \text{Day 1} & \text{Day 2} & \text{Day 3} \\ \hline 1 & 2 & & \\ 2 & 1 & & \\ 3 & 4 & & \\ 4 & 3 & & \end{array}

now we should conquer the result. upper side of table didn't play with down site of table so we should schedule their matches, and remove team 4. then we have

\begin{array}{c|ccc} & \text{Day 1} & \text{Day 2} & \text{Day 3} \\ \hline 1 & 2 & 3 & - \\ 2 & 1 & - & 3 \\ 3 & - & 1 & 2\\ \end{array}

now we have table for 3 teams it's time to schedule 6 teams so we create table like this

\begin{array}{c|cccccc} & \text{Day 1} & \text{Day 2} & \text{Day 3} & \text{Day 4} & \text{Day 5} & \text{Day 6}\\ \hline 1 & 2 & 3 & - & & & \\ 2 & 1 & - & 3 & & & \\ 3 & - & 1 & 2 & & & \\ 4 & 5 & 6 & - & & & \\ 5 & 4 & - & 6 & & & \\ 6 & - & 4 & 5\\ \end{array}

for conquer step we should schedule match for upper side of table with down side so then

\begin{array}{c|cccccc} & \text{Day 1} & \text{Day 2} & \text{Day 3} & \text{Day 4} & \text{Day 5} & \text{Day 6}\\ \hline 1 & 2 & 3 & - & 4 & 5 & 6\\ 2 & 1 & - & 3 & 5 & 6 & 4 \\ 3 & - & 1 & 2 & 6 & 4 & 5 \\ 4 & 5 & 6 & - &1 &2 &3 \\ 5 & 4 & - & 6 &2 & 3& 1\\ 6 & - & 4 & 5 & 3 & 1 & 2\\ \end{array}

but it's not best answer and we can reschedule rest matches such that tournament end in 5 days for $n = 6$. how can I modify conquer step?

Answer 1

The recursive approach is not necessarily the simplest one here. There is a simple direct construction I am quoting from here. Suppose first that you are trying to schedule $n$ teams, where $n$ is odd. In total there are $n(n-1)/2$ matches to schedule, and in each round at most $(n-1)/2$ matches can take place, so there should be $n$ rounds in total. All computations below are modulo $n$. In round $r$, team $x$ plays against team $r-x$, except for team $r/2$, which stays out. Here is an example for $n=5$:

• Round 0: 1–4, 2–3, 0 sits out
• Round 1: 0–1, 2–4, 3 sits out
• Round 2: 0–2, 3–4, 1 sits out
• Round 3: 0–3, 1–2, 4 sits out
• Round 4: 0–4, 1–3, 2 sits out

It's easy to prove the correctness of this schedule. Indeed, teams $x$ and $y$ meet in round $x+y$ and in no other round.

If $n$ is even then there are $n(n-1)/2$ matches to schedule, and each round at most $n/2$ can take place, so there should be $n-1$ rounds. Indeed, we take the schedule for $n-1$, and pair up the team sitting out with the extra team. For example, for $n=6$:

• Round 0: 1–4, 2–3, 0–5
• Round 1: 0–1, 2–4, 3–5
• Round 2: 0–2, 3–4, 1–5
• Round 3: 0–3, 1–2, 4–5
• Round 4: 0–4, 1–3, 2–5

It's again not hard to prove the correctness of the schedule. If $x,y \neq n-1$ then they meet in round $x+y$, while $x$ and $n-1$ meet in round $2x$ (where all computations are modulo $n-1$).

Answer 2

I think this method will fix conquer step. for example for 6 teams we have this table when we divide it to 2 piece

\begin{array}{c|cccccc} & \text{Day 1} & \text{Day 2} & \text{Day 3} & \text{Day 4} & \text{Day 5} & \text{Day 6}\\ \hline 1 & 2 & 3 & - & & & \\ 2 & 1 & - & 3 & & & \\ 3 & - & 1 & 2 & & & \\ 4 & 5 & 6 & - & & & \\ 5 & 4 & - & 6 & & & \\ 6 & - & 4 & 5\\ \end{array}

first we should replace rested games with new matches, we now that the only answer for Day 3 of team 1 is 4 so we put 4 in table and so on then we have \begin{array}{c|cccccc} & \text{Day 1} & \text{Day 2} & \text{Day 3} & \text{Day 4} & \text{Day 5} & \text{Day 6}\\ \hline 1 & 2 & 3 & 4 & & & \\ 2 & 1 & 5 & 3 & & & \\ 3 & 6 & 1 & 2 & & & \\ 4 & 5 & 6 & 1 & & & \\ 5 & 4 & 2 & 6 & & & \\ 6 & 3 & 4 & 5\\ \end{array}

then we will create array like this $[4,5,6]$ cause we put the numbers with this order, then we remove first element and add it to end of list, then we write this numbers for Day 4 and it will so we have this

\begin{array}{c|cccccc} & \text{Day 1} & \text{Day 2} & \text{Day 3} & \text{Day 4} & \text{Day 5} & \text{Day 6}\\ \hline 1 & 2 & 3 & 4 & 5 & & \\ 2 & 1 & 5 & 3 & 6 & & \\ 3 & 6 & 1 & 2 & 4 & & \\ 4 & 5 & 6 & 1 & 3 & & \\ 5 & 4 & 2 & 6 & 1 & & \\ 6 & 3 & 4 & 5 & 2 & & \\ \end{array}

and do it again, we should do this $\frac{n-2}{2}$ times when $\frac{n}{2}$ is odd and $\frac{n}{2}$ times when $\frac{n}{2}$ is even. so the final table will be like this \begin{array}{c|cccccc} & \text{Day 1} & \text{Day 2} & \text{Day 3} & \text{Day 4} & \text{Day 5} & \text{Day 6}\\ \hline 1 & 2 & 3 & 4 & 5 & 6 & \\ 2 & 1 & 5 & 3 & 6 & 4 & \\ 3 & 6 & 1 & 2 & 4 & 5 & \\ 4 & 5 & 6 & 1 & 3 & 3& \\ 5 & 4 & 2 & 6 & 1 & 2& \\ 6 & 3 & 4 & 5 & 2 & 1 & \\ \end{array}

it should be a valid table because divide part are correct and adding matches to rest parts are also correct the conquer part has no repeated match with games in day 1 to $\frac{n}{2}$ because the right side of table are matches between the upper side of table with down side of table and the only matches that may case repeated match is matches that we add to rest matches. we use list and shifting it circular so it will guarantee that we don't have any repeated match.

I check this method for $n < 2000$ and it was correct.

Answer 3

For example we have 8 teams: 1 2 3 4 5 6 7 8 Divide they onto 2 groups and let play each team one group with each team another group:

day 1: 1 2 3 4 5 6 7 8 day 2: 1 2 3 4 6 7 8 5 day3: 1 2 3 4 7 8 5 6 day 4: 1 2 3 4 8 5 6 7

All teams one group just had games with all teams another group. But teams inside one group didn't have game between each other.

Repeat that algorithm recursively for every group

day 5: 1 2 5 6 3 4 7 8 day 6: 1 2 5 6 4 3 8 7

Once again divide every group

day 7: 1 3 5 7 2 4 6 8

Perfect solution : Recursion algorithm here