Listing off players in a tournament such that each player won against the next?

Question

Given a class with N people(This is represented by an array int[] a), where each person plays a game with all other people. Each game will involve only 2 players. So for N people there will be total NC2 games.

Results are with you for all the games. You have to arrange each and every person in a queue with a condition that, a[i] should have won game with a[i-1]. THis is true for all values of i.

We don’t need to care about the result between a[i] and a[i-2] . a[i] may win or lose the game with a[i-2].

My Approach( I used backtracking to solve this problem) :

• For each person we will maintain a list of people who won the game with that person.
• A new result array will be created(Length equal to the total players).
• 1st position is filled up iteratively with each person.
• Next position in the result array is filled up with the person who won game with previous person. This person will be picked up from corresponding winning list of previous person by iterating over that array.

Above solution will try each and every path using recursive approach. Isn't there any better algorithm ?

Answer 1

Mathematically what you have is something called a tournament graph and you are trying to find a Hamiltonian path inside of that tournament graph. Although in an arbitrary graph the problem of finding a Hamiltonian path is NP-hard, it's known that every tournament graph must have a Hamiltonian path and fortunately they're not that hard to find.

One simple approach is to use recursion. If there's only one node in the graph, it's pretty simple to solve this problem: just list off the one person in the graph. Otherwise, choose some node arbitrarily. Split the tournament into to sub-tournaments: one of all the people who beat that person and one of all the people that person lost to. Recursively get a Hamiltonian path in each of those sub-tournaments. Then, concatenate the Hamiltonian paths together, putting the person you singled out in the first step in the proper place in between them.

So just how efficient is this algorithm? Like quicksort, the efficiency of the algorithm depends on how you split the tournament a smaller pieces. Suppose that when you choose a person to split the tournament into smaller pieces, you choose the person whose number of wins is as close to n/2 to as possible. This will produce two smaller tournament of size roughly n/2. Determining which person to pick takes quadratic time, because you have to look at the outcome of each game to count of how many wins and losses player has. This gives us the following recurrence relation:

T(n) = 2T(n/2) + O(n²)

Using the master theorem, we get that this recurrence solves to O(n²), which is considerably faster than your initial idea.

Hope this helps!

Answer 2

Here is a hint:

Suppose we already have an ordering for the first i-1 people that satisfies the constraint. Is it always possible to insert person i into this list somewhere?

Consider the cases: either person i beat all of the first i-1 people, or none of them, or some of them but not all of them. Where can person i be inserted in the first 2 cases? (It may help to assign a 1 or 0 to each of the i-1 people in the list so far, indicating whether that person beat person i.) In the third case, we can insert person i between any person that they beat and any person that beat them. Does such a pair always exist? If not, is there anywhere else where we are guaranteed to be able to safely insert person i?