Round robin tournament scheduling using divide and conquer

Problem Detail: 

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?

Asked By : Karo

Answered By : Karo

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/33459