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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.