Algorithm: finding the biggest element of a list

Question

The catch: only comparisons between elements of the list is allowed. For example, suppose we have 1,000,000 chess players, and we are assigned the task of finding the best chess player in the group. We can play one chess player against any other chess player. Now, we want to minimize the maximum number of games any player plays.

If player A beats player B, and B beats C, we can assume that A is better than C. What is the smallest n such that no player plays more than n games?

@Carl: This is not homework; it's actually a subproblem of a larger problem from SPOJ.

Answer 1

I would wager a guess that the answer is the binary log of the number of people.

You set up a binary tree as a tournament ladder. This means the most games anyone plays is the height of the tree. The height of the binary tree would be log n

Answer 2

As far as I know there is no algorithm to solve your problem without any additional outside information to rank the players (such as seeding). If you could seed the players appropriately you can find the best player in less rounds than the worst case suggested by J. Wong.

Example of the results of 2 rounds of 10 players: A is the best, ceil(log 10) = 4

A > B; C > D; E > F; G > H; I > J

A > C; B > E; F > G; D > I

Answer 3

How do I find the biggest element of a list

If the list is ordered, then the biggest element is the first (or last) element of the list.

If the list is not ordered then:

Element biggest = list.get(0);
for (Element e : list) {
    if (e.compareWith(biggest) > 0) {
        biggest = e;
    }
}

---

For example, suppose we have 1,000,000 chess players, and we are assigned the task of finding the best chess player in the group. Now, we want to minimize the maximum number of games any player plays.

With the new constraint of the last sentence ...

Answer #1: zero games played. Compare the chess player's rankings and the one with the best ranking is the objectively best player ... according to the ranking.

Answer #2: at most ceiling(log2(nos_players)) games played per player. A "knock out" / elimination tournament eliminates half the players in each round, so the number of rounds and hence the maximum number of games played by any one player is ceiling(log2(nos_players)).

The corresponding algorithm is trivially:

List players = ...
while (players.size() > 1) {
    List winners = new ArrayList();
    Iterator it = players.iterator();
    while (it.hasNext()) {
        Player p1 = it.next();
        if (it.hasNext()) {
            Player p2 = it.next();
            int result = p1.compareTo(p2);
            if (result < 0) {
                winners.add(p2);
            } else if (result > 0) {
                winners.add(p1);
            } else {
                throw new Exception("draws are impossible in chess");
            }
        } else {
            winners.add(p1); // bye
        }
    }
    players = winners;
}

(Aside: if you also have a predetermined ranking for the players and the number of players N is at least 2 less than ceiling(log2(N)), you can arrange that the best 2 players get a bye in one round. If the best 2 players meet in the final, then everyone will have played less than ceiling(log2(N)) games ... which is an improvement on the solution where the byes are allocated randomly.)

In reality, answer #2 does not work for the game of chess because it does not take account of the fact that a significant percentage of real chess games are draws; i.e. neither player wins. Indeed, the fact that player A beat player B in one game does not mean A is a better player than B. To determine who is the better of any two players they need to play a number of games and tally the wins and losses. In short, the notion that there is a "better than" relation for chess players is TOTALLY unrealistic.

---

Not withstanding the points above, knock-out is NOT a practical way to organize a chess tournament. Everyone will be camped out on the tournament organizer's desk complaining about having to play games against players much better (or worse) than themselves.

The way a real chess (or similar) tournament works is that you decide on the number of rounds you want to play first. Then in a "round-robin" tournament, you select the top N players by ranking. and arrange that each player plays each other player. The player with the best win / draw score is the winner, and in the event of a tie you use (say) "sum of opponents scores" as a tie breaker. There are other styles of tournament as well that cater for more players / less rounds.

Answer 4

Instead of building an Abstract Data Structure such as a binary tree and resolving a tournament, you could re-interpret your goal in a different light:

Eliminate all the elements on the list that are not the largest

You will find that doing this may be much more algorithmically expedient than building a tree and seeding a "tournament".

I can demonstrate that eliminating all elements on a list that are not the largest can be done with a worst-case scenario of log n calls/comparisons per element.

Work on a copy of your original list if possible.

1. Pair off consecutive elements and remove from the list the lower-valued of the two. Ignore the unpaired element, if there is one.

   This can be done by iterating from 0 <= i < int(n/2) and comparing indices 2i and 2i+1.

   i.e., for n=7, int(n/2) = 3, i = 0,1,2; compare indices 0 and 1, 2 and 3, 4 and 5.

2. There should be a total of int(n/2) indices eliminated. Subtract that count from n. Then, repeat 1 until there is only one index remaining. This will be your largest.

Here is an implementation in Ruby:

def find_largest(list)

  n = list.size
  working_list = list.clone()

  while n > 1

    temp_list = Array.new()

    for i in (0...n/2)          # remember to cast n/2 to integer if not automatic
      if working_list[2*i] > working_list[2*i+1]
        new_list.push(working_list[2*i])
      else
        new_list.push(working_list[2*i+1])
      end
    end

    working_list = temp_list

    n -= n/2                    # remember to cast n/2 to integer if not automatic

  end

  return working_list[0]

end

Answer 5

None of the other answers answers this correctly (i.e. if I understood the question correctly).

All they have done is to show an algorithm to achieve the logarithmic bound. This only proves that it is only an upper bound and not the minimum possible.

In fact, we can show that the logn bound is optimal, by showing that in the worst case, any algorithm which uses comparisons has to compare the maximum element at least ceil(logn) times, i.e. no matter how you conduct the tournament, there would be cases (depending on your algorithm) which will have the winner play at least that many games.

To show this assume each player started out with 1$. Now each time two people play, the loser hands over all his money to the winner.

In the end, the winner gets all the money! If there were two people with non-zero amounts of money, that means they haven't lost a game yet and haven't played against each other and so the winner is not decided yet.

Now consider the case, where it so happens that the player with the lower amount of money always loses. (If they had equal non-zero amounts, you can take the player with smaller player number loses and if they both are zero (both lost some game ealier), you can decide what the consistent outcome is, based on the past games.)

In this case, the winner will at most double his money in each game, and thus would need to play at least ceil(logn) games.

The fact that this bound is achievable is clear from the other answers.

Incidentally, this lower bound proof can probably be modified to show that in the worst case you require at least n + ceil(logn) - 1 total comparisons to find the largest and second largest elements.