Volteo de prefijo

Definición

Operación que invierte el orden de los primeros $k$ elementos de una secuencia y deja intactos los restantes.

Equivale a introducir una pala debajo del elemento en la posición $k$ y voltear de una sola vez toda la parte que está encima.

F_{k} (a_{1}, \dots, a_{k}, a_{k + 1}, \dots, a_{n}) = (a_{k}, \dots, a_{1}, a_{k + 1}, \dots, a_{n}), 1 \leq k \leq n .

La operación es su propia inversa:

F_{k} (F_{k} (A)) = A .

F_{3} ([2, 4, 1, 3]) = [1, 4, 2, 3] .

Intercambiar dos elementos cualesquiera no es un volteo de prefijo. Tampoco lo es invertir un segmento que comienza después de la primera posición.

¿Qué costo debe asignarse al volteo: una operación física o $Θ (k)$ movimientos en una representación de arreglo?

tags	concepto, algoritmos, operaciones
aliases	Pancake flip, Inversión de prefijo