¿Existe un algoritmo de "clasificación" que devuelve una permutación aleatoria cuando se utiliza un comparador de monedas?

Inspirado por esta pregunta en la que el autor de la pregunta quiere saber si el tiempo de ejecución cambia cuando el comparador utilizado en un algoritmo de búsqueda estándar se reemplaza por un lanzamiento de moneda justo, y también por la falla prominente de Microsoft al escribir un generador de permutación uniforme, mi pregunta es así :

¿Existe un algoritmo de clasificación basado en la comparación que, según nuestra implementación del comparador:

1. devolver los elementos en orden ordenado cuando se utiliza un comparador verdadero (es decir, la comparación hace lo que esperamos en un algoritmo de clasificación estándar)
2. devuelve una permutación uniformemente aleatoria de los elementos cuando el comparador se reemplaza por un lanzamiento de moneda justo (es decir, devuelve x < y = truecon probabilidad 1/2, independientemente del valor de x e y)

El código para el algoritmo de clasificación debe ser el mismo. Es solo el código dentro de la "caja negra" de comparación que está permitido cambiar.

El siguiente algoritmo determinista (sin el comparador) funciona para una tupla de entrada :$(a_1,\dots,a_n)$

1. Foro de la Fisher-Yates barajar la utilización de su comparador con algún par estático (digamos ) (muestreo de aceptación-rechazo haciendo) como una moneda al aire. Si el comparador genera 1 por primera vez, úselo invertido para evitar un bucle de rechazo sin fin en el caso determinista.$a_1 < a_2$$1$
2. (aceleración opcional: pruebe un solo par veces, donde n es la longitud o su entrada. Si cualquiera de las dos salidas difiere, devuelva la permutación obtenida en (1))$n$$n$
3. Ordene su matriz usando merge sort.

Dada una relación de orden determinista como comparador, este algoritmo clasifica una matriz en el tiempo ya que la mezcla aleatoria de Fisher-Yates se ejecuta en O ( n ) utilizando la máxima O ( log n ) "bits aleatorios" no aleatorios (por ejemplo, llamadas a su comparador ) en cada paso y el orden de fusión tiene la misma complejidad asintótica. El resultado de (1) es totalmente inútil en este caso, pero dado que es seguido por un tipo real, esto no hace daño.$\mathcal{O}(n \log n)$$\mathcal{O}(n)$$\mathcal{O}(\log n)$

Dado un lanzamiento de moneda real, el comparador (1) permuta la matriz con la misma probabilidad para cada permutación y si realmente tiene que hacer (3) (omitió (2) o (2) no pudo determinar la aleatoriedad), esto no es daño porque la distribución de su resultado solo depende del orden de su entrada que se distribuye uniformemente entre todas las permutaciones debido a (1), por lo que el resultado de todo el algoritmo también se distribuye uniformemente. El número de veces que se debe repetir cada muestreo de aceptación-rechazo se distribuye geométricamente (rechazar con probabilidad ) y por lo tanto tiene un valor esperado<2. Cada repetición usa como máximolognbits, por lo que el análisis de tiempo de ejecución es casi el mismo que en el caso determinista, pero solo obtenemos untiempodeejecución esperadodeO(nlogn), con la posibilidad de no terminación (terminacasi con seguridad).$< \frac{1}{2}$$< 2$$\log n$$\mathcal{O}(n \log n)$

---

Como señaló Joe: si no le gusta la prueba para el primer bit en (1), haga (3) luego (1) y use que siempre es 0 , ya que la matriz ya está ordenada en caso determinista Además, debe restar su número aleatorio del límite superior en el rango en el bucle, porque el límite superior para el número aleatorio produce la permutación idéntica. Pero tenga en cuenta que (2) está prohibido entonces, porque siempre tiene que barajar en el caso de rescate.$a_n < a_1$$0$

---

Incluso puede usar las mismas llamadas a su comparador para (1) y (3), pero luego demostrar que el resultado se distribuye uniformemente es al menos mucho más difícil, si es posible.

---

El siguiente algoritmo no tiene fases distintas para barajar y ordenar, pero es asintóticamente más lento. Es esencialmente una ordenación por inserción con búsqueda binaria . Usaré para denotar la entrada y b k = ( b k , 1 , ... , b k , k ) para denotar el resultado después de la ronda k :$a=(a_1,\dots,a_n)$$b_k=(b_{k,1},\dots,b_{k,k})$$k$

1. Conjunto $b_{1,1} = a_1$
2. $a_2 < a_1$$b_2 = (a_2,a_1)$$(c,d):= (2,1)$$b_2 = (a_1,a_2)$$(c,d):= (1,2)$$a_d < a_c$$0$
3. $b_{k}$$k \geq 3$$b_{k-1}$
4. $l=\lceil log_2 k \rceil$$k' = 2^l$$k'$$2$$k$
5. $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. $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. $b_n$

$k-1$$k$

Tenga en cuenta que este algoritmo es ineficiente en ambos modos en comparación con la ordenación aleatoria y de fusión de Fisher-Yates, ya que insertar un elemento en una posición arbitraria es costoso si se usa una matriz y la búsqueda binaria necesita tiempo lineal si se usa una lista. Pero quizás una modificación de la ordenación del montón o la ordenación del árbol de manera similar podría conducir a un algoritmo más rápido.

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