Aquí hay un documento al respecto: Un algoritmo simple en el lugar para In-Shuffle (enlace pdf).
El problema es mucho más difícil de lo que parece. La respuesta de Naveen tuvo el enfoque correcto, pero supuso que un solo ciclo cubrirá todos los números, lo cual no es cierto. La permutación para organizar la matriz de longitud 8 tiene un ciclo de descomposición de (0) (124) (365) (7). (Ver notación de ciclo)
Para resumir el artículo:
1) Resuelva el problema por una longitud con descomposiciones de ciclo fáciles.
– Las matrices de longitud 3 ^ k – 1 pueden descomponerse en k ciclos disjuntos que comienzan en 3 ^ i para i en {0, …, k-1}. Esos ciclos se pueden cambiar individualmente para colocar los elementos en su posición correcta.
2) Aplique recursivamente eso para resolver la longitud arbitraria de la matriz.
– Si la matriz está representada por las submatrices A1 + A2 + A3 + A4, donde A1 + A3 tiene una longitud de 3 ^ k – 1, puede invertir A2 + A3 y luego invertirlas individualmente para obtener A1 + A3 + A2 + A4. Ahora puede ejecutar el primer paso en A1 + A3 y recurrir en A2 + A4.
- Cómo explicar efectivamente el algoritmo en una entrevista técnica
- ¿Por qué las entrevistas tecnológicas se centran en problemas o algoritmos complicados de la estructura de datos cuando la mayoría de las empresas no requieren esto en el trabajo diario?
- Cómo reorganizar una matriz determinada para que Arr [I] se convierta en Arr [Arr [I]] con O (1) espacio adicional
- ¿Cuál es la explicación y la prueba de la codiciosa solución en esta pregunta?
- ¿Qué haría si no sabe cómo resolver las preguntas del algoritmo en una entrevista técnica?
Editar: ese documento aparentemente resuelve un problema diferente, 012345 -> 304152, en lugar de 012345 -> 031425. Pero en realidad podemos reducir este problema al problema en el papel al cambiar dos números de marcador de posición: 012xy345 -> y031425x. (o simplemente intercambie cada dos elementos antes de comenzar como se sugiere en los comentarios: 304152 -> 031425)