Algorithm: finding the biggest element of a list

The catch: only comparisons between elements of the list is allowed. For example, suppose we have 1,000,000 chess players, and we are assig开发者_开发问答ned 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.

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

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.

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

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