Recherche dans l'espace des permutations

On me donne n objets, et un ensemble de n permutations de ces n objets (sur n! Permutations totales). Il y a une vraie permutation sous-jacente, dont je sais qu'elle fait partie de l'ensemble des n permutations, mais je ne sais pas laquelle. Un oracle connaît cependant la véritable permutation. Pour trouver la vraie permutation, je suis autorisé à interroger l'oracle pour une comparaison par paire entre 2 objets (est un avant b dans la vraie permutation?).

Une stratégie naïve serait de faire une recherche binaire (poser la «bonne» question de comparaison par paire qui élimine la moitié des permutations à chaque étape), pour trouver la vraie permutation en log n étapes. Ma question est, cela peut-il toujours être fait? Ou puis-je trouver un ensemble de permutations contradictoires telles que les requêtes O (log n) ne suffisent pas.

Edit:
Exemple: disons que mes objets sont 1,2,3,4. L'ensemble des permutations est {1243, 2341, 1342, 3412}. Je ne connais pas la vraie permutation. Je demande "Est-ce que 2 avant 4 est dans la vraie permutation?". L'oracle revient oui. Je sais donc que c'est parmi les deux premières permutations. Je demande alors "Est-ce que 1 avant 3 est dans la vraie permutation?" pour trouver la vraie permutation.

complexity-theory lower-bounds search-problem permutations elexhobby
la source

1) L'oracle met en œuvre une relation d'ordre complète? 2) Je suppose que la "vraie" permutation est le minimum ou le maximum de cette relation? 3) Avant de pouvoir effectuer une recherche binaire, vous devez trier. 4) Trouver un minimum resp. le maximum est possible en temps linéaire. 5) Étant donné que l'ensemble d'entrée n'est pas ordonné, vous ne pouvez pas échapper à la vérification de chaque permutation d'entrée au moins une fois, donc une limite inférieure linéaire est triviale. 6) Tout cela suppose que vous ne savez rien de la relation d'ordre; si vous savez quelque chose, vous pourrez peut-être l'utiliser.

Raphael

@Raphael: Ma question n'était pas claire comme je l'avais écrit plus tôt. Voyez si l'exemple que j'ai ajouté aide. Je suis préoccupé par le nombre de requêtes que vous devez poser à l'oracle.

elexhobby

Si je comprends le problème, je pense que cet ensemble ne peut pas être coupé en deux avec une seule paire 213456 124356 123465 132456 124356 123546.

Louis

une question intéressante serait de savoir quel sous-ensemble de permutations la borne liée serait-elle suffisante?

Nikos M.

Considérez l'ensemble suivant de $n$ ordres, que je donne pour $n = 6$ :

123456 213456 132456 124356 123546 123465

$123456 \\ 213456 \\ 132456 \\ 124356 \\ 123546 \\ 123465$ Espérons que la généralisation à l'arbitraire

n

$n$ est clair.

Si vous ne comparez jamais $i$ et $i+1$ alors vous ne pouvez pas distinguer la permutation $1$ par permutation $i+1$ . Cela signifie que vous avez besoin d'au moins $n-1$ des comparaisons (ce n'est pas un argument, mais il peut être converti en un seul); c'est serré (pour cet exemple).

Permettez-moi également de mentionner deux articles bien connus dans le domaine:

Fredman a montré que s'il y a $\Gamma$ de nombreuses commandes possibles, alors vous pouvez trouver la bonne en utilisant $\log_2 \Gamma + 2n$ requêtes.
Kahn et Kim ont montré que si les commandes potentielles constituent toutes les commandes possibles prolongeant une commande partielle, alors $O(\log \Gamma)$ les requêtes suffisent.

Yuval Filmus
la source

Recherche dans l'espace des permutations

Réponses: