# Searching the space of permutations

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.

• 1) The oracle implements a complete order relation? 2) I take it the "true" permutation is the minimum or maximum of that relation? 3) Before you can binary search you have to sort. 4) Finding a minimum resp. maximum is possible in linear time. 5) Given that the input set is unordered, you can not escape checking each input permutation at least once, so a linear lower bound is trivial. 6) That all assumes that you don't know anything about the order relation; if you do know something, you may be able to utilize that. – Raphael Apr 10 '15 at 16:28
• @Raphael: My question was unclear as I'd written earlier. See if the example I added helps. I'm concerned with the number of queries you must ask the oracle. – elexhobby Apr 10 '15 at 16:38
• If I understand the problem, then I think this set can't be cut in half with any single pair 213456 124356 123465 132456 124356 123546. – Louis Apr 10 '15 at 16:43
• an interesting question would be for what subset of permutations would the log bound be sufficient? – Nikos M. Apr 15 '15 at 19:38

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).
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.