[Solved]: Searching the space of permutations

Problem Detail: 

I'm given n objects, and a set of n permutations of these n objects (out of n! total permutations). There is a true underlying permutation, which I know is one among the set of n permutations, but I don't know which one. An oracle however knows the true permutation. To find the true permutation, I'm allowed to query the oracle for pairwise comparison between 2 objects (is a before b in the true permutation?).

A naive strategy would be to do a binary search (ask the "right" pairwise comparison question that eliminates half the permutations at every stage), to find the true permutation in log n steps. My question is, can this always be done? Or can I find an adversarial set of permutations such that O(log n) queries aren't enough.

Edit:
Example: Say my objects are 1,2,3,4. The set of permutations is {1243, 2341, 1342, 3412}. I don't know the true permutation. I ask "Is 2 before 4 in the true permutation?". The oracle returns yes. So I know its among the first two permutations. I then ask "Is 1 before 3 in the true permutation?" to find the true permutation.

Asked By : elexhobby

Answered By : Yuval Filmus

Consider the following set of $n$ orders, which I give for $n = 6$: $$ 123456 \\ 213456 \\ 132456 \\ 124356 \\ 123546 \\ 123465 $$ Hopefully the generalization to arbitrary $n$ is clear.

If you never compare $i$ and $i+1$ then you cannot tell apart permutation $1$ from permutation $i+1$. This means that you need at least $n-1$ comparisons (this is not an argument, but it can be converted to one); this is tight (for this example).

Let me also mention two well-known papers in the area:

1. Fredman showed that if there are $\Gamma$ many possible orderings, then you can find the correct one using $\log_2 \Gamma + 2n$ queries.

2. Kahn and Kim showed that if the potential orderings constitute all possible orderings extending some partial order, then $O(\log \Gamma)$ queries suffice.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/41222

3.2K people like this

 Download Related Notes/Documents