Ordenar una matriz bidimensional codificada llena de números intercambiando números adyacentes [cerrado]

9

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.

JCarter
fuente
¿Es este un problema de rompecabezas, velocidad o golf?
Michael Klein
@MichaelKlein Esto es un rompecabezas.
JCarter
¿Está anotado? ¿Qué rangos deben manejarse?
Michael Klein
1
@steveverrill Me temo que es bastante imposible resolver el ejemplo n = 10 en menos de 100 intercambios (o incluso 1000; pero demuéstrame que estoy equivocado). Aún así, el número de swaps es el criterio ganador (¡aunque el cálculo debe ser factible!), El que encuentre una solución con el menor número de swaps gana.
JCarter
1
@JCarter ¿Creo que querías decir que solo se pueden intercambiar números adyacentes?
quintopia

Respuestas:

3

Mathematica, no golf

towards[a_,b_]:={a,a+If[#==0,{0,Sign@Last[b-a]},{#,0}]&@Sign@First[b-a]};
f[m_]:=Block[{m2=Map[QuotientRemainder[#-1,10]+1&,m,{2}]},
  Rule@@@Apply[10(#1-1)+#2&,#,{2}]&@
    Reap[Table[
      m2=NestWhile[
        Function[{x},x/.(Sow[#];Thread[#->Reverse@#])&[x[[##]]&@@@towards[First@Position[x,i,{2}],i]]]
        ,m2,#~Extract~i!=i&];
      ,{i,Reverse/@Tuples[Range[10],2]}];][[2,1]]]

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 towardsda 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); y towards[{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,

{1->76,1->34,1->35,1->88,1->41,11->16,11->69,11->46, ...

Para una configuración aleatoria, el número total de intercambios es 558.5 ± 28.3 (1σ).

ingrese la descripción de la imagen aquí

njpipeorgan
fuente