Existe-t-il un algorithme de «tri» qui renvoie une permutation aléatoire lors de l'utilisation d'un comparateur à pièces?

9

Inspiré par cette question dans laquelle le demandeur veut savoir si le temps d'exécution change lorsque le comparateur utilisé dans un algorithme de recherche standard est remplacé par un coin-flip équitable, et aussi l' échec de Microsoft pour écrire un générateur de permutation uniforme, ma question est donc :

Existe-t-il un algorithme de tri basé sur la comparaison qui, selon notre implémentation du comparateur:

  1. renvoyer les éléments dans l'ordre trié lors de l'utilisation d'un vrai comparateur (c'est-à-dire que la comparaison fait ce que nous attendons dans un algorithme de tri standard)
  2. retourner une permutation uniformément aléatoire des éléments lorsque le comparateur est remplacé par un lancer de pièce équitable (c'est-à-dire, retourner x < y = trueavec une probabilité 1/2, quelle que soit la valeur de x et y)

Le code de l'algorithme de tri doit être le même. Seul le code à l'intérieur de la comparaison "boîte noire" est autorisé à changer.

Joe
la source
Voir aussi cette question .
Raphael
2
Voir aussi la question intéressante suivante: cstheory.stackexchange.com/questions/5321/… .
Yuval Filmus
1
Voulez-vous que votre comparateur aléatoire se comporte bien? Voici deux manières possibles. (1) Une fois que le comparateur décide que x<y , alors x<y toujours, et aussi y>x . (2) Idem, mais si de plus le comparateur décide que x<y et y<z , alors il s'engage sur x<z (et z>x ). Dans les deux cas, chaque requête non contrainte est toujours complètement aléatoire.
Yuval Filmus
@YuvalFilmus Je veux essentiellement ce qui est demandé dans votre question liée, sauf que le même circuit devrait également trier si nous remplaçons la porte aléatoire par une porte de comparaison-échange qui commande la paire d'éléments.
Joe
1
Voir ici pour de belles visualisations.
Raphael

Réponses:

3

L'algorithme déterministe suivant (sans le comparateur) fonctionne pour un tuple d'entrée :(a1,,an)

  1. Faites le mélange Fisher-Yates en utilisant votre comparateur avec une paire statique (disons ) comme un retournement de pièces (en faisant un échantillonnage d'acceptation-rejet). Si le comparateur sort 1 la première fois, utilisez-le inversé pour éviter une boucle de rejet sans fin dans le cas déterministe.a1<a21
  2. (accélération facultative: essayez une seule paire fois, où n est la longueur ou votre entrée. Si deux des sorties diffèrent, renvoyez la permutation obtenue en (1))nn
  3. Triez votre tableau à l'aide du tri par fusion.

Étant donné une relation d'ordre déterministe en tant que comparateur, cet algorithme trie un tableau dans le temps puisque le shuffle de Fisher-Yates s'exécute dans O ( n ) en utilisant des "bits aléatoires" non aléatoires O ( log n ) maximaux (par exemple, des appels à votre comparateur ) à chaque étape et tri par fusion a la même complexité asymptotique. Le résultat de (1) est totalement inutile dans ce cas, mais comme il est suivi d'une sorte réelle, cela ne fait pas de mal.O(nlogn)O(n)O(logn)

Étant donné un véritable lancer de pièce comme comparateur (1) permute le tableau avec une probabilité égale pour chaque permutation et si vous devez vraiment faire (3) (vous avez omis (2) ou (2) n'a pas réussi à déterminer le caractère aléatoire), ce n'est pas mal parce que la distribution de son résultat ne dépend que de l'ordre de son entrée qui est uniformément répartie entre toutes les permutations en raison de (1), donc le résultat de l'algorithme entier est également uniformément distribué. Le nombre de répétitions de chaque échantillonnage d'acceptation-rejet est géométriquement distribué (rejet avec probabilité ) et a donc une valeur attendue<2. Chaque répétition utilise au pluslognbits, donc l'analyse de l'exécution est presque la même que dans le cas déterministe, mais nous n'obtenons qu'uneexécution attenduedeO(nlogn), avec la possibilité de non-terminaison (ne se termine quepresque sûrement).<12<2lognO(nlogn)


Comme Joe l'a souligné: si vous n'aimez pas le test pour le premier bit de (1), faites (3) puis (1) et utilisez qui est toujours 0 , car le tableau est déjà trié dans le cas déterministe. De plus, vous devez soustraire votre nombre aléatoire de la limite supérieure de la plage de la boucle, car la limite supérieure du nombre aléatoire donne la permutation identique. Mais sachez que (2) est alors interdit, car vous devez toujours faire le mélange dans le cas de la rançon.an<a10


Vous pouvez même utiliser les mêmes appels vers votre comparateur pour (1) et (3), mais prouver que le résultat est uniformément distribué est au moins beaucoup plus difficile, si possible du tout.


L'algorithme suivant n'a pas de phases distinctes à mélanger et à trier, mais est asymptotiquement plus lent. Il s'agit essentiellement d'un tri par insertion avec recherche binaire . Je vais utiliser pour désigner l'entrée et b k = ( b k , 1 , , b k , k ) pour désigner le résultat après le k- ème tour:a=(a1,,an)bk=(bk,1,,bk,k)k

  1. Set b1,1=a1
  2. Si alors b 2 = ( a 2 , a 1 ) et ( c , d ) : = ( 2 , 1 ) sinon b 2 = ( a 1 , a 2 ) et ( c , d ) : = ( 1 , 2 ) . Dans les deux cas, un d <a2<a1b2=(a2,a1)(c,d):=(2,1)b2=(a1,a2)(c,): =(1,2) sera toujours 0 (c'est-à-dire faux) pour un comparateur non aléatoire.une<unec0
  3. Pour obtenir pour k 3, obtenir d'abord b k - 1 .bkk3bk-1
  4. Soit et k = 2 l , c'est-à-dire que k est la plus petite puissance de 2 non inférieure à k .l=log2kk=2lk2k
  5. Soit . Pour tout j { 1 , , l } soit i j = { i j - 1 + 2 l - j i j - 1 + 2 l - j > k - 1 a d < a c i j - 1 i j - 1 + 2 l -je0=0j{1,,l}
    ij={ij1+2ljij1+2lj>k1ad<acij1ij1+2lj>k1¬(ad<ac)ij1+2ljij1+2ljk1bk1,ij1+2lj<akij1ij1+2ljk1¬(bk1,ij1+2lj<ak)
  6. Si répéter (5.) sinon b k = ( b k - 1 , 1 , , b k - 1 , i l - 1 , a k , b k - 1 , i l , , b k - 1 , k - 1 )il>kbk=(bk1,1,,bk1,il1,ak,bk1,il,,bk1,k1)
  7. Sortie bn

Cas aléatoire: 5 + la clause if de 6 est essentiellement un échantillonnage d'acceptation-rejet. Le reste de l'algorithme est un shuffle naïf: mélangez les premiers éléments et ajoutez le k- ème élément à chaque position avec une probabilité égale. Si nous utilisions le tri par insertion normal, nous obtiendrions une distribution binomiale à la place.k1k

Notez que cet algorithme est inefficace dans les deux modes par rapport au tri aléatoire et de fusion Fisher-Yates car l'insertion d'un élément dans une position arbitraire est coûteuse si vous utilisez un tableau et la recherche binaire nécessite un temps linéaire si vous utilisez une liste. Mais peut-être qu'une modification du tri en tas ou du tri en arbre d'une manière similaire pourrait conduire à un algorithme plus rapide.

frafl
la source
@Joe, pouvez-vous mettre tous vos points encore valides pour le message dans la forme actuelle dans un commentaire et supprimer le reste?
frafl
J'espérais un algorithme qui ne ferait pas d'étapes différentes selon le comparateur utilisé. Pouvez-vous éviter une boucle de rejet infinie sans sonder le comparateur? Je pense que vous pourriez éviter le rejet en effectuant d'abord l'étape (3) ...
Joe
i
Premier commentaire: Notez que je ne jette pas ce premier échantillon, c'est "dual use". J'ai pensé à inverser tous les 2 bits, mais cela n'empêcherait pas la boucle sans fin. En fait, un modèle irrégulier est nécessaire et peut même rejeter beaucoup plus d'entrées. Bien sûr, je pourrais XOR les deux bits les plus récents au lieu du premier et du plus récent, mais ce n'est pas vraiment différent.
frafl
ian<a10
4

n2UNE/2B1/n!n>21/n!UNE/2B

Yuval Filmus
la source
1
Mais cela ne vaut que si nous avons besoin d'une limite déterministe sur l'exécution, ce qui n'était pas demandé dans la question. Si nous voulons seulement que le temps d'exécution attendu soit fini, cela ne devrait poser aucun problème.
frafl
1
Connaissez-vous un algorithme de tri raisonnable qui ne se termine pas en temps polynomial?
Yuval Filmus
2
Vous mélangez le cas déterministe et aléatoire. L'algorithme peut se terminer en temps polynomique déterministe s'il est appelé avec une relation d'ordre déterministe et en temps polynomial attendu s'il est appelé avec une pièce comme comparateur.
frafl
2k
kUNE/2k