Durchsuchen des Permutationsraums

Ich bekomme n Objekte und eine Menge von n Permutationen dieser n Objekte (von n! Gesamtpermutationen). Es gibt eine echte zugrunde liegende Permutation, von der ich weiß, dass sie eine unter den n Permutationen ist, aber ich weiß nicht, welche. Ein Orakel kennt jedoch die wahre Permutation. Um die wahre Permutation zu finden, darf ich das Orakel zum paarweisen Vergleich zwischen zwei Objekten abfragen (steht a vor b in der wahren Permutation?).

Eine naive Strategie wäre, eine binäre Suche durchzuführen (stellen Sie die "richtige" paarweise Vergleichsfrage, bei der in jeder Phase die Hälfte der Permutationen eliminiert wird), um die wahre Permutation in log n Schritten zu finden. Meine Frage ist, kann das immer gemacht werden? Oder kann ich einen kontroversen Satz von Permutationen finden, sodass O (log n) -Abfragen nicht ausreichen?

Bearbeiten:
Beispiel: Angenommen, meine Objekte sind 1,2,3,4. Der Satz von Permutationen ist {1243, 2341, 1342, 3412}. Ich kenne die wahre Permutation nicht. Ich frage "Ist 2 vor 4 in der wahren Permutation?". Das Orakel gibt ja zurück. Ich weiß also, dass es sich um eine der ersten beiden Permutationen handelt. Ich frage dann "Ist 1 vor 3 in der wahren Permutation?" um die wahre Permutation zu finden.

$n$$n = 6$

$i$$i+1$$1$$i+1$$n-1$

Lassen Sie mich auch zwei bekannte Artikel in der Region erwähnen:

1. $\Gamma$$\log_2 \Gamma + 2n$

2. $O(\log \Gamma)$