Pesquisando no espaço de permutações

Recebi n objetos e um conjunto de n permutações desses n objetos (de n! Permutações totais). Existe uma verdadeira permutação subjacente, que eu sei que é uma entre o conjunto de n permutações, mas não sei qual. Um oráculo, no entanto, conhece a verdadeira permutação. Para encontrar a permutação verdadeira, tenho permissão para consultar o oráculo para comparação por pares entre dois objetos (a antes b na permutação verdadeira?).

Uma estratégia ingênua seria fazer uma pesquisa binária (faça a pergunta de comparação em pares "certa" que elimina metade das permutações em cada estágio), para encontrar a verdadeira permutação nas etapas do log n. Minha pergunta é: isso sempre pode ser feito? Ou posso encontrar um conjunto de permutações contraditório, de modo que as consultas O (log n) não sejam suficientes.

Edit:
Exemplo: Digamos que meus objetos sejam 1,2,3,4. O conjunto de permutações é {1243, 2341, 1342, 3412}. Não conheço a verdadeira permutação. Eu pergunto "2 antes das 4 está na verdadeira permutação?". O oráculo retorna sim. Então eu sei que está entre as duas primeiras permutações. Eu então pergunto "1 antes das 3 está na verdadeira permutação?" para encontrar a verdadeira permutação.

Considere o seguinte conjunto de $n$ ordens, que eu dou para $n = 6$:

Se você nunca comparar $i$ e $i+1$ então você não pode distinguir permutação $1$ de permutação $i+1$. Isso significa que você precisa de pelo menos$n-1$comparações (este não é um argumento, mas pode ser convertido em um); isso é apertado (para este exemplo).

Permitam-me mencionar também dois trabalhos conhecidos na área:

1. Fredman mostrou que, se houver$\Gamma$ pedidos possíveis, você pode encontrar o correto usando $\log_2 \Gamma + 2n$ consultas.

2. Kahn e Kim mostraram que, se os pedidos em potencial constituem todos os pedidos possíveis, estendendo alguma ordem parcial,$O(\log \Gamma)$ consultas são suficientes.