8
$\begingroup$

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.

Improve this question
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Raphael♦ Apr 10 '15 at 16:28
  • $\begingroup$ @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. $\endgroup$ – elexhobby Apr 10 '15 at 16:38
  • 2
    $\begingroup$ 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. $\endgroup$ – Louis Apr 10 '15 at 16:43
  • $\begingroup$ an interesting question would be for what subset of permutations would the log bound be sufficient? $\endgroup$ – Nikos M. Apr 15 '15 at 19:38
8
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.