Knobelaufgabe?

[tedlemegba]

Hallo zusammen!

Heute kam mir ein Problem, es hat eigentlich keinen Praxisbezug (zumindest fällt mir gerade keiner ein).

Nehmen wir für ein anschauliches Beispiel an, ich habe 24 Objekte (etwa gleiche Größe). Diese sind durchnummeriert (unterscheiden sich als). Ordnen wir sie in einem zweidimensionalen Feld an:

[FONT="Courier New"]+----+----+----+----+----+----+----+----+
| 12 | 10 |  9 |  7 |  1 | 22 |  4 | 18 |
+----+----+----+----+----+----+----+----+
|  2 |  3 |  8 | 19 | 17 | 20 | [B][I]14[/I][/B] | 11 |
+----+----+----+----+----+----+----+----+
|  5 |  6 | 13 | 15 | 16 | [B][I]21[/I][/B] | [B]23[/B] | [B][I]24[/I][/B] |
+----+----+----+----+----+----+----+----+[/FONT]

Ist es möglich von dieser Verteilung auf eine beliebige andere Verteilung zu kommen, wenn - beispielsweise mit einem Roboter mit Greifarm - immer nur benachbarte Felder vertauscht werden dürfen? Zum Beispiel 23 mit 14, 23 mit 24 oder 23 mit 21 (aber nicht 23 mit 20 oder 11 = diagonal).


Oder allgemeiner:
Ist es bei n Objekten möglich sie von einer der n! möglichen Verteilungen (in einem n Einheiten langen und m Einheiten breiten zweidimensionalen Feld) möglich zu jeder beliebigen anderen der n! möglichen Verteilungen durch obigen Tauschprozess zu kommen?

Oder ergeben sich etwa Abhängigkeiten? Spielt vielleicht auch die Länge n oder Breite m eine Rolle; müssten sie zum Beispiel ungerade sein?

Hat jemand eine Ahnung, ob es einen mathematischen Ansatz für das "Problem" gibt? Ansonsten auch euch viel Spaß beim knobeln.

 

[Tyrell]

Ja, ist es. Der Praxisbezug wäre hier z.B. das Sortieren von Folgen. Man kann es mathematisch beweisen, der Ansatz wäre ähnlich wie bei BubbleSort.

edit: Anderer Ansatz wäre Routing auf Gitternetzwerken.

 

[Talion]

So, wie du die Aufgabe gestellt hast, ist es möglich sein. Im ersten Moment erinnerte es mich aber an ein Rätsel von Loyd, das unlösbar und dem deinen nicht ganz unähnlich ist.