Pesquisando no espaço de permutações

8

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.

elexhobby
fonte
1) O oráculo implementa uma relação completa de ordem? 2) Entendo que a permutação "verdadeira" é o mínimo ou o máximo dessa relação? 3) Antes de poder pesquisar binariamente, você deve classificar. 4) Encontrando um mínimo de resp. o máximo é possível em tempo linear. 5) Dado que o conjunto de entradas não está ordenado, não é possível deixar de verificar cada permutação de entrada pelo menos uma vez, portanto, um limite inferior linear é trivial. 6) Que tudo pressupõe que você não sabe nada sobre a relação de ordem; se você souber algo, poderá utilizá-lo.
Raphael
@ Rafael: Minha pergunta não estava clara como eu escrevi anteriormente. Veja se o exemplo que adicionei ajuda. Estou preocupado com o número de perguntas que você deve fazer ao oráculo.
precisa saber é o seguinte
2
Se eu entender o problema, então eu acho que este conjunto não pode ser cortado ao meio com um único par de 213456 124356 123465 132456 124356 123546.
Louis
uma pergunta interessante seria para que subconjunto de permutações o log vinculado seria suficiente?
Nikos M.

Respostas:

8

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

123456213456132456124356123546123465
Esperemos que a generalização para arbitrária n está claro.

Se você nunca comparar Eu e Eu+1 então você não pode distinguir permutação 1 de permutação Eu+1. Isso significa que você precisa de pelo menosn-1comparaçõ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Γ pedidos possíveis, você pode encontrar o correto usando registro2Γ+2n consultas.

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

Yuval Filmus
fonte