Buscando el espacio de permutaciones

Me dan n objetos, y un conjunto de n permutaciones de estos n objetos (de n! Permutaciones totales). Hay una verdadera permutación subyacente, que sé que es una entre el conjunto de n permutaciones, pero no sé cuál. Sin embargo, un oráculo conoce la verdadera permutación. Para encontrar la permutación verdadera, se me permite consultar el oráculo para la comparación por pares entre 2 objetos (¿es a antes de b en la permutación verdadera?).

Una estrategia ingenua sería hacer una búsqueda binaria (haga la pregunta de comparación por pares "correcta" que elimine la mitad de las permutaciones en cada etapa), para encontrar la permutación verdadera en los pasos log n. Mi pregunta es, ¿se puede hacer esto siempre? ¿O puedo encontrar un conjunto de permutaciones de confrontación tal que las consultas O (log n) no sean suficientes.

Editar:
Ejemplo: Digamos que mis objetos son 1,2,3,4. El conjunto de permutaciones es {1243, 2341, 1342, 3412}. No sé la verdadera permutación. Pregunto "¿Está 2 antes de 4 en la verdadera permutación?". El oráculo devuelve sí. Entonces sé que está entre las dos primeras permutaciones. Luego pregunto "¿Está 1 antes de 3 en la verdadera permutación?" para encontrar la verdadera permutación.

Considere el siguiente conjunto de $n$ órdenes, que doy por $n = 6$:

Si nunca comparas $i$ y $i+1$ entonces no puedes distinguir la permutación $1$ de permutación $i+1$. Esto significa que necesitas al menos$n-1$comparaciones (esto no es un argumento, pero se puede convertir en uno); Esto es apretado (para este ejemplo).

Permítanme mencionar también dos documentos conocidos en el área:

1. Fredman demostró que si hay$\Gamma$ muchos pedidos posibles, entonces puede encontrar el correcto usando $\log_2 \Gamma + 2n$ consultas

2. Kahn y Kim demostraron que si los posibles pedidos constituyen todos los posibles pedidos que se extienden a un orden parcial, entonces$O(\log \Gamma)$ Las consultas son suficientes.