Una matriz bidimensional de tamaño n × n se llena con n * n números, comenzando por el número 1. Esos números se deben ordenar por fila en orden ascendente; el primer número de una fila debe ser mayor que el último número de la fila anterior (el número más pequeño de todos (1) estará en [0,0]). Esto es similar al 15 rompecabezas .
Esto es, por ejemplo, una matriz ordenada de tamaño n = 3 .
1 2 3
4 5 6
7 8 9
Entrada
La entrada es una matriz codificada. Puede ser de cualquier tamaño hasta n = 10. Ejemplo para n = 3:
4 2 3
1 8 5
7 9 6
Salida
Salida de una lista de intercambios necesarios para ordenar la matriz Un intercambio se define de la siguiente manera: dos números adyacentes intercambian posiciones, ya sea horizontal o verticalmente; el intercambio diagonal no está permitido.
Ejemplo de salida para el ejemplo anterior:
- Intercambiar 4 y 1
- Intercambiar 8 y 5
- Intercambiar 8 y 6
- Intercambiar 9 y 8
Cuantos menos intercambios se requieran, mejor. El tiempo de cálculo debe ser factible.
Aquí hay otro ejemplo de entrada, con n = 10:
41 88 35 34 76 44 66 36 58 28
6 71 24 89 1 49 9 14 74 2
80 31 95 62 81 63 5 40 29 39
17 86 47 59 67 18 42 61 53 100
73 30 43 12 99 51 54 68 98 85
13 46 57 96 70 20 82 97 22 8
10 69 50 65 83 32 93 45 78 92
56 16 27 55 84 15 38 19 75 72
33 11 94 48 4 79 87 90 25 37
77 26 3 52 60 64 91 21 23 7
Si no me equivoco, esto requeriría alrededor de 1000-2000 swaps.
Respuestas:
Mathematica, no golf
Explicacion :
El algoritmo es similar a "ordenar burbujas". Estos 100 números se ordenan uno por uno
1, 11, 21, ..., 91; 2, ..., 92; ...; 10, ..., 100
,. Primero se mueven hacia arriba / abajo a las filas correctas, y luego se mueven hacia la izquierda a las columnas correctas.La función
towards
da las dos posiciones para intercambiar. Por ejemplo, si se{5,2}
está moviendo a{1,1}
,towards[{5,2},{1,1}]
da{{5,2},{5,1}}
(subir); ytowards[{5,1},{1,1}]
da{{5,1},{4,1}}
(mover a la izquierda).Resultados :
Para el caso de prueba, el número total de intercambios es de 558. Los primeros intercambios son,
Para una configuración aleatoria, el número total de intercambios es 558.5 ± 28.3 (1σ).
fuente