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.