Finding the order of a set's elements
Posted
by
Maciej Stachowski
on Programmers
See other posts from Programmers
or by Maciej Stachowski
Published on 2013-11-02T21:23:02Z
Indexed on
2013/11/02
22:15 UTC
Read the original article
Hit count: 279
algorithms
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?
© Programmers or respective owner
