1
$\begingroup$

I'm struggling with a divide and conquer algorithm for the Tennis Tournament (or Round Robin tournament).

I can successfully build a timetable if $N$ (number of players) is $2^k=N$, but Brassard-Bratley, Fundamentals of Algorithmics suggests that is possible to build a divide and conquer algorithm for an arbitrary number of players.

However, I can't find a rule to build such timetables.

For example, an N=4 is very easy to schedule. Divide by two, do tournaments, then merge each one on the left with each one on the right:

|1|2|3|4|
|-------|
|1-2|3-4|
|-------|
|1-3 2-4|
|1-4 2-3|

With N=5, I have problems because the parts of the division by two have different sizes

|1|2|3|4|5|
|---------|
|1-2|3-4  |
| - |3-5  |
| - |4-5  |
|---------|
|1-5 2-4  |
|1-3 2-5  |

And of course in the empty spaces, you could put 1-4 and 2-3, but I don't know how to generalize this.

And if N=7, there are no empty spaces and just fills perfectly.

|1|2|3|4|5|6|7|
|-------------|
|1-2  |4-5|6-7|
|     |-------|
|2-3  |4-6|5-7|
|1-3  |4-7|5-6|
|-------------|
|1-4 2-5 3-6  |
|1-5 2-6 3-7  |
|1-6 2-7 3-4  |
|1-7 2-4 3-5  |

So, what's the general rule to follow in a divide and conquer approach to the tennis tournament?

$\endgroup$
  • $\begingroup$ Can you explain your goal more formally? Tennis tournament is not a standard term in combinatorics. $\endgroup$ – Yuval Filmus Jan 7 at 18:14
  • $\begingroup$ @YuvalFilmus it's a round robin tournament (en.wikipedia.org/wiki/Round-robin_tournament?wprov=sfla1, has algorithm but it's not divide and conquer). But I've seen the term Tennis Tournament also in this site to refer to this problem. Sorry for the confusion $\endgroup$ – Adrián Arroyo Calle Jan 7 at 18:20
  • 2
    $\begingroup$ Given that the form of the desired answer depends on the parity of $n$, it is somewhat less natural to consider a divide-and-conquer approach for general $n$; the case of powers of 2 is more natural. That's probably what the book meant. $\endgroup$ – Yuval Filmus Jan 7 at 19:15

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.