Ein zweidimensionales Array der Größe n × n wird ausgehend von Nummer 1 mit n * n Zahlen gefüllt. Diese Zahlen sind pro Zeile in aufsteigender Reihenfolge zu sortieren; Die erste Zahl einer Zeile muss größer sein als die letzte Zahl der vorherigen Zeile (die kleinste Zahl von allen (1) steht in [0,0]). Dies ähnelt dem 15-Puzzle .

Dies ist beispielsweise ein sortiertes Array der Größe n = 3 .

1 2 3
4 5 6
7 8 9

Eingang

Die Eingabe ist ein verschlüsseltes Array. Es kann eine beliebige Größe bis zu n = 10 haben. Beispiel für n = 3:

4 2 3
1 8 5
7 9 6

Ausgabe

Geben Sie eine Liste der zum Sortieren des Arrays erforderlichen Swaps aus . Ein Swap ist wie folgt definiert: Zwei benachbarte Nummern tauschen Positionen entweder horizontal oder vertikal aus; Diagonales Tauschen ist nicht erlaubt.

Beispielausgabe für das obige Beispiel:

• Tauschen Sie 4 und 1
• Tauschen Sie 8 und 5
• Tauschen Sie 8 und 6
• Tauschen Sie 9 und 8

Je weniger Swaps erforderlich sind, desto besser. Die Rechenzeit muss machbar sein.

Hier ist eine weitere Beispieleingabe mit 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

Wenn ich mich nicht irre, würde dies ungefähr 1000-2000 Swaps erfordern.

Mathematica, nicht Golf gespielt

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]]]

Erklärung :

Der Algorithmus ähnelt der "Blasensortierung". Diese 100 Zahlen werden nacheinander in die richtige Reihenfolge gebracht 1, 11, 21, ..., 91; 2, ..., 92; ...; 10, ..., 100. Sie werden zuerst nach oben / unten in die richtigen Zeilen und dann nach links in die richtigen Spalten verschoben.

Funktion towardsgibt die beiden Positionen zu tauschen. Wenn sich zum Beispiel {5,2}bewegt {1,1}, towards[{5,2},{1,1}]gibt {{5,2},{5,1}}(nach oben bewegen); und towards[{5,1},{1,1}]gibt {{5,1},{4,1}}(nach links bewegen).

Ergebnisse :

Für den Testfall beträgt die Gesamtzahl der Swaps 558. Die ersten Swaps sind:

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

Für eine zufällige Konfiguration beträgt die Gesamtzahl der Swaps 558,5 ± 28,3 (1σ).