I\'m given n objects, and a set of n permutations of these n objects (out of n!

Question

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.

Explanation / Answer

Consider the following set of n orders, which I give for n=6:
123456213456132456124356123546123465
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:

Fredman showed that if there are ? many possible orderings, then you can find the correct one using log2?+2n queries.

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

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.