Finding the order of a set's elements
- by Maciej Stachowski
A little rephrased, in the form of a game, real-life problem:
Suppose there is a set of elements {1, 2, ..., n}. Player A has chosen a single permutation of this set. Player B wants to find out the order of the elements by asking questions of form "Is X earlier in the permutation than Y?", where X and Y are elements of the set.
Assuming B wants to minimize the amount of questions, how many times would he have to ask, and what would be the algorithm?