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

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.

L'algorithme déterministe suivant (sans le comparateur) fonctionne pour un tuple d'entrée :$(a_1,\dots,a_n)$

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.$a_1 < a_2$$1$
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))$n$$n$
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.$\mathcal{O}(n \log n)$$\mathcal{O}(n)$$\mathcal{O}(\log n)$

É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).$< \frac{1}{2}$$< 2$$\log n$$\mathcal{O}(n \log n)$

---

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.$a_n < a_1$$0$

---

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=(a_1,\dots,a_n)$$b_k=(b_{k,1},\dots,b_{k,k})$$k$

1. Set $b_{1,1} = a_1$
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$a_2 < a_1$$b_2 = (a_2,a_1)$$(c,d):= (2,1)$$b_2 = (a_1,a_2)$$(c,d):= (1,2)$ sera toujours 0 (c'est-à-dire faux) pour un comparateur non aléatoire.$a_d < a_c$$0$
3. Pour obtenir pour k ≥ 3, obtenir d'abord b k - 1 .$b_{k}$$k \geq 3$$b_{k-1}$
4. Soit et k ′ = 2 l , c'est-à-dire que k ′ est la plus petite puissance de 2 non inférieure à k .$l=\lceil log_2 k \rceil$$k' = 2^l$$k'$$2$$k$
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 $i_0 = 0$$j \in \{1,\dots,l\}$ $$i_j = \begin{cases} i_{j-1} + 2^{l-j} & i_{j-1} + 2^{l-j} > k-1 \wedge a_d < a_c\\ i_{j-1} & i_{j-1} + 2^{l-j} > k-1 \wedge \neg (a_d < a_c)\\ i_{j-1} + 2^{l-j} & i_{j-1} + 2^{l-j} \leq k-1 \wedge b_{k-1,i_{j-1} + 2^{l-j}} < a_k \\ i_{j-1} & i_{j-1} + 2^{l-j} \leq k-1 \wedge \neg(b_{k-1,i_{j-1} + 2^{l-j}} < a_k) \\ \end{cases}$$
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$i_l > k$$b_k=(b_{k-1,1},\dots,b_{k-1,i_l -1},a_k,b_{k-1,i_l},\dots,b_{k-1,k-1})$
7. Sortie $b_n$

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.$k-1$$k$

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.

$n \leq 2$$A/2^B$$1/n!$$n > 2$$1/n!$$A/2^B$