Algoritmo de desplazamiento aleatorio de tiempo lineal en el lugar

15

¿Hay un algoritmo de tiempo aleatorio lineal en el lugar? Este es el algoritmo que algunas manos especialmente hábiles son capaces de realizar: dividir uniformemente una matriz de entrada de tamaño par y luego intercalar los elementos de las dos mitades.

Mathworld tiene una breve página sobre riffle shuffle . En particular, estoy interesado en la variedad de reproducción aleatoria que transforma la matriz de entrada 1 2 3 4 5 6 en 1 4 2 5 3 6. Tenga en cuenta que, en su definición, la longitud de entrada es .2n

Es sencillo realizar esto en tiempo lineal si tenemos una segunda matriz de tamaño o más útil. Primero copie los últimos elementos a la matriz. Luego, suponiendo una indexación basada en 0, copie los primeros elementos de los índices a . Luego copie los elementos de la segunda matriz de nuevo a la matriz de entrada, asignando índices [0,1,2, ..., n-1] a [1,3,5, ..., 2n-1] . (Podemos hacer un poco menos de trabajo que eso, porque el primer y el último elemento de la entrada no se mueven).nnn[0,1,2,...,n1][0,2,4,...,2n2]n[0,1,2,...,n1][1,3,5,...,2n1]

Una forma de intentar hacer esto en el lugar implica la descomposición de la permutación en ciclos disjuntos, y luego reorganizar los elementos de acuerdo con cada ciclo. Nuevamente, suponiendo una indexación basada en 0, la permutación involucrada en el caso de 6 elementos es

σ=(012345024135)=(0)(5)(1243).

Como se esperaba, el primer y el último elemento son puntos fijos, y si permutamos los 4 elementos del medio, obtenemos el resultado esperado.

Desafortunadamente, mi comprensión de las matemáticas de las permutaciones (y su LATEX ) se basa principalmente en wikipedia, y no sé si esto se puede hacer en tiempo lineal. ¿Quizás las permutaciones involucradas en esta mezcla pueden descomponerse rápidamente? Además, ni siquiera necesitamos la descomposición completa. Bastará con determinar un solo elemento de cada uno de los ciclos disjuntos, ya que podemos reconstruir el ciclo a partir de uno de sus elementos. Tal vez se requiere un enfoque completamente diferente.

Los buenos recursos en las matemáticas relacionadas son tan valiosos como un algoritmo. ¡Gracias!

Johny
fuente
Hay una solución de tiempo (con espacio extra). No conozco ninguna solución de tiempo lineal. O ( 1 )O(nlgn)O(1)
Radu GRIGore
44
Eso es más apropiado para cs.stackexchange. En el modelo no uniforme, veces siempre es posible. En este caso, debería ser posible incluso de manera uniforme. O(n)
Yuval Filmus
1
@Radu Similar a esta pregunta , este problema probablemente no tenga una solución usando solo espacio extra, sino espacio extra. O ( log n )O(1)O(logn)
Tyson Williams
2
¡Acepto mi comentario (y voto para cerrar)! (Aunque la pregunta se responde en la literatura.)
Yuval Filmus
1
Escuché esta pregunta de un estudiante de CS la semana pasada, quien la escuchó en una entrevista de trabajo.
Jeffε

Respuestas:

12

El problema es sorprendentemente no trivial. Aquí hay una buena solución de Ellis y Markov, In-Situ, Stable Merging a través de Perfect Shuffle (sección 7). Ellis, Krahn y Fan, Computing the Cycles in the Perfect Shuffle Permutation logran seleccionar "líderes del ciclo", a expensas de más memoria. También se relaciona el bonito artículo de Fich, Munro y Poblete, Permuting In Place , que proporciona un algoritmo general de tiempo para el modelo oracle. Si solo está disponible un oráculo para la permutación, el algoritmo requiere espacio logarítmico; Si también tenemos un oráculo para el inverso, requiere un espacio constante.O(nlogn)

Ahora para la solución de Ellis y Markov. Primero, supongamos que . Luego, calcular la combinación aleatoria perfecta de orden reduce a calcular la combinación aleatoria perfecta de órdenes e , con una rotación que los precede. Aquí hay una prueba con un ejemplo ( , , ): n x y n = 5 x = 3 y = 2 012 345 67 89 012 567 34 89 051627 3849n=x+ynxyn=5x=3y=2

012345678901256734890516273849

Ellis y Markov encontraron una manera fácil de calcular la combinación perfecta cuando , usando espacio constante y tiempo lineal. Con esto, obtenemos un algoritmo para calcular la combinación perfecta para arbitraria . Primero, escriba usando la codificación binaria de , y deje que . Gire los bits del medio , baraje los bits del lado derecho . Ignorando los bits de la derecha , gire los bits del medio y baraje los la derecha n n = 2 k 0 + + 2 k w n n i = 2 k i + + 2 k w n 0n=2knn=2k0++2kwnni=2ki++2kwn0 2 k 0 n 1 2 k 1 O ( n 0 + + n w ) = O ( n ) n t + 12k02k0n12k1bits Y así. Tenga en cuenta que la rotación es fácil ya que los primeros elementos rotados funcionan como líderes del ciclo. La complejidad total de la rotación es , ya que . La complejidad total de las internas es .O(n0++nw)=O(n)O ( 2 k 0 + + 2 k w ) = O ( n )nt+1<nt/2O(2k0++2kw)=O(n)

Queda por mostrar cómo calcular la combinación perfecta cuando . De hecho, podremos identificar líderes de ciclo, siguiendo el trabajo clásico sobre collares (Fredricksen y Maiorana, collares de cuentas en colores y secuencias de -ary de Bruijn ; Fredricksen y Kessler, un algoritmo para generar collares de cuentas en dos colores )k kn=2kkk

¿Cuál es la conexión? Afirmo que la permutación aleatoria corresponde al desplazamiento a la derecha de la representación binaria. Aquí hay una prueba, por ejemplo, para : Por lo tanto, para encontrar líderes de ciclo, necesitamos encontrar un representante de cada clase de equivalencia de la rotación de cadenas binarias de longitud . Los documentos mencionados anteriormente dan el siguiente algoritmo para generar todos los líderes del ciclo. Comience con . En cada paso, estamos en algún punto . Encuentre el índice máximo de un bit cero,000 001 010 011n=8

000001010011100101110111000100001101010110011111
k0ka1akikpor para obtener , y que el siguiente punto sea . Siempre que , la nueva cadena es un líder de ciclo.ik=di+r(a1ai11)da1arr=0

Por ejemplo, cuando esto genera la secuencia 0000 , 0001 , 0010 , 0011 , 0101 , 0110 , 0111 , 1111 .n=16

0000,0001,0010,0011,0101,0110,0111,1111.

Los líderes del ciclo se destacan.

Yuval Filmus
fuente
3
Ver también la respuesta de Aryabhata, que usa arxiv.org/abs/0805.1598 . Ese documento, "Un algoritmo simple en el lugar para In-Shuffle" de Jain, usa la misma idea, pero en lugar de poderes de , usa poderes de 3 . El punto es que dado que 2 es un módulo raíz primitivo 3 k , se ve fácilmente que 3 0 , ... , 3 k son líderes del ciclo. ¡Incluso más simple que Ellis y Markov! 2323k30,,3k
Yuval Filmus
Aunque creo que el trabajo de Jain es un poco más directo, prefiero el trabajo anterior, así como la publicación anterior con más votos.
Johny
2

metronorte=metro-2yoF(yo)=2yoyonorte/ /2F(yo)=2(yomodificaciónnorte/ /2)-1yo>norte/ /2

O(1)O(Iniciar sesiónnorte)

Robert Robere
fuente
Ah, espera Esto supone que todos los valores en la permutación del riff se encuentran en el mismo ciclo. Esta estrategia tendría que modificarse un poco, dependiendo de cuántos ciclos disjuntos haya.
Robert Robere