1
$\begingroup$

So, I was tasked with creating an app that generates the schedule of a doubles tennis tournament (i.e., teams of two) in a way that, by the end of it, everyone would have played against the rest of the players. The trick is every team should change in each round so that not only everyone played against everyone but the teams are not repeated.

I've tried implementing it using greedy search with backtracking, but it just takes too long to find a valid solution, so what I'm asking for is sugerences of an algorithm more efficient that I can use to solve this problem. This are the especifics of the problem:

  • There is a multiple of 4 number 'n' of players.
  • There is at least n/4 fields to play, so that in each round all players have a match.
  • No player can play twice with the same partner, so in each round the teams must change.
  • No player can play twice against the same opponent. At the end of the tournament, each player must have played against the rest.

    The algorithm must search the ideal combination of matchs so it meets the requeriments above.

    Any ideas? Thank you in advance.

EDIT 2: It's not possible for 4 players.

ROUND 1

  • Player 1 & Player 2 vs Player 3 & Player 4

So far so good.

ROUND 2

  • Player 1 & Player 3 vs Player 2 & Player 4

Player 1 already played against Player 4, not a valid solution. The other possibility:

ROUND 2'

  • Player 1 & Player 4 vs Player 2 & Player 3

Player 1 already played against Player 3, not a valid solution either.

EDIT: It is double tennis, sorry for the misunderstanding. Each player must have played against the rest, but it's not mandatory that each player ended up playing with the rest. Question edited for clarity.

$\endgroup$
3
  • $\begingroup$ Welcome to Computer Science! Your question is very well written. I have a question. If "there is an even number 'n' of players", don't you need n/2 fields to play at the same time for a round instead of n/4 fields? Do you mean doubles match? If there is no need to play at the same time, why is one field not enough? $\endgroup$
    – John L.
    Oct 18, 2018 at 13:13
  • $\begingroup$ Can you list an ideal solution for 4 players? or even for 6 players? That would clarify a few details. $\endgroup$
    – John L.
    Oct 18, 2018 at 13:35
  • $\begingroup$ Yes, it is double tennis, and there must be a multiple of 4 number of players. Sorry for the misunderstanding. $\endgroup$ Oct 18, 2018 at 15:36

1 Answer 1

1
$\begingroup$

Sorry, but there is no solution. (Assuming that all games are 2 vs 2.)

How many matches does each player play?

  • They play with each other player exactly once, one such player per match, for a total of $n-1$ matches.
  • They play against each other player exactly once, two such players per match, for a total of $\frac{n-1}{2}$ matches.

This implies $n-1=\frac{n-1}{2}$ and thus $n=1$. But you said $n$ is even. And besides, a single-player tournament would not be interesting.

[EDIT]

The question was now changed to omit the requirement that every other player is a partner at least once. However, it is still not possible.

How many rounds should there be? For every player there are $n-1$ potential opponents. In every round there are $2$ opponents without repetition. Hence the number of rounds is $\frac{n-1}2$. This is not an integer number, because $n$ is even.

$\endgroup$
3
  • $\begingroup$ Hum, I see it. I think I got tangled in my own thoughts. What I really wanted to ask about was if it's possible,and what's the best method if it is, to do it so everyone plays against everyone and the teams don't have repeated members, it's not neccesary that they play WITH everyone. I've made the trace for 4 players, and it doesn't seem possible, I'll try for eight now. $\endgroup$ Oct 18, 2018 at 15:24
  • $\begingroup$ @PedroSorianoRuiz, if you have any partial result such as "it doesn't seem possible for 4 players", please include them in your question. People are not expected to check comment. Your partial result will save people lots of time and motivate them to answer. $\endgroup$
    – John L.
    Oct 18, 2018 at 16:55
  • $\begingroup$ Thanks for the advice. Trace added to the post. Working on the trace for 8 players now, I feel like it's not possible, but I'd like to prove it for n players. $\endgroup$ Oct 18, 2018 at 17:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.