Para mi sorpresa, no pude encontrar documentos sobre esto, probablemente busqué las palabras clave incorrectas.
Entonces, tenemos una variedad de cualquier cosa, y una función en sus índices; es una permutación.
¿Cómo reordenamos la matriz de acuerdo con con memoria y tiempo de ejecución tan cerca de y como sea posible?
¿Existen condiciones adicionales cuando esta tarea se vuelve más fácil? Por ejemplo, cuando sabemos explícitamente que una función es la inversa de ?
Sé de un algoritmo que sigue ciclos y recorre un ciclo para que cada índice verifique si es el menor en su ciclo, pero nuevamente, tiene el peor tiempo de ejecución de , aunque en promedio parece comportarse mejor ...
Respuestas:
Opción 0: Permuting In Place (1995) de Faith E. Fich, J. Ian Munro, Patricio V. Poblete tiempo espacio.O(nlogn) O(log2n)
Opción 1: Haga trampa comprimiendo su permutación a una estructura de datos sucinta, consulte Munro http://www.itu.dk/people/ssrao/icalp03-a.pdf .
Opción 2: use una descomposición del ciclo principal para almacenar la permanente de manera sucinta y use ese espacio adicional para hacer trampa http://oeis.org/A186202
Opción 3: realizar un seguimiento del índice más grande de cada ciclo manipulado. Para cada iteración, use el índice invisible más grande para mover todo en su ciclo por uno. Si llega a un índice visto, deshaga todo ese trabajo porque el ciclo ya ha sido manipulado. tiempo, espacio.O(n2) O(#cycles∗logn)
Opción 4: realice un seguimiento del índice más grande de cada ciclo manipulado, pero solo hágalo en lotes de distintas duraciones de ciclo. Para cada iteración, use el índice invisible más grande para mover todo en su ciclo por uno. Si llega a un índice visto, deshaga todo ese trabajo porque el ciclo ya ha sido manipulado. tiempo, espacio.O(n2∗distinct_cycle_lengths) O((#cycles_with_same_size)∗logn)
Opción 5: del mismo documento de Munro que la Opción 0, para gire el ciclo de si es el índice más grande en ese ciclo. tiempo y espacio.i=1..n p(i) i O(n2) O(logn)
fuente
Si usa la representación de ciclo de la permutación, necesita 1 elemento de matriz adicional para almacenar el elemento que se está permutando actualmente y puede ejecutar los ciclos en operaciones peores O (N).
fuente
Cualquier permutación de N elementos se puede convertir a cualquier otra permutación utilizando N-1 o menos intercambios. El peor de los casos para este método puede requerir llamadas O (n ^ 2) al oráculo, F (). Comience desde la posición más baja. Sea x la posición que estamos intercambiando actualmente.
Si F (x)> = x, intercambie las posiciones xy F (x). De lo contrario, debemos encontrar dónde está actualmente el elemento que estaba en la posición F (x) en la lista. Podemos hacer esto con la siguiente iteración. Deje y = F (x). Hacer hasta y> = x: y = F (y): Fin Do. Ahora intercambie las posiciones x e y.
fuente
Este método usa el inverso de F y requiere n bits de almacenamiento. Si x es la posición de un elemento en la matriz original, deje que G (x) sea la posición del elemento en la matriz ordenada. Deje B ser una matriz de n bits. Establezca todos los n bits de B en 0.
PARA x = 1 a n-1: SI B (x) == 0 ENTONCES: y = G (x): HAGA HASTA x == y: Intercambie las posiciones x e y: B (y) = 1: y = G ( y): LOOP: ENDIF: NEXT X
Este método sigue intercambiando el elemento actualmente en la posición x a la posición final del elemento. El bucle interno termina cuando el elemento correcto se cambia a la posición x. Dado que cada intercambio mueve al menos un elemento a la posición final del elemento, el bucle interno Do no puede ejecutarse más de n-1 veces durante la ejecución. Creo que este método es O (n) tiempo y espacio.
fuente