Wie kann ich die Reihenfolge einer Stuhlreihe effektiv anpassen?

Wissenschaft Mathematik
#1

Hallo, das Thema hat nicht primär mit Mathematik zu tun, aber ich finde keine bessere Kategorie. Falls es hier einen Admin gibt, darf der Beitrag gerne in eine geeignetere Kategorie verschoben werden :wink:

Zum Thema:
Angenommen ich habe eine Stuhlreihe von 1 - 10:
1 2 3 4 5 6 7 8 9 10

Die Anordnung/Reihenfolge soll aber folgendermaßen geändert werden:
7 3 10 1 4 2 5 9 6 8

Geplantes Vorgehen:
Ich nehme Stuhl 1, stelle ihn zur Seite und „parke ihn zwischen“.
Somit wird Platz für Stuhl 7.
Stuhl 7 war auf Position 7, somit wird Platz für Stuhl 5.
Stuhl 5 war auf Position 5, somit wird Platz für Stuhl 4.
Stuhl 4 war auf Position 4, somit wird Platz für Stuhl 1.
Stop!
Das Prozess kommt jetzt ins Stocken, weil ich jetzt mit Stuhl 1 weitermachen muss der eigentlich bis zum Schluss geparkt sein sollte.

Gibt es eine Formel oder einen Trick, wie ich raus bekomme welchen Stuhl ich zu Beginn zur Seite stellen muss, damit ich mit dem beschriebenen Vorgehen bis zum Schluss durch komme und sozusagen als allerletzter Schritt der zur Seite gestellte Stuhl seinen Platz bekommt.

In diesem Beispiel mit 10 Stühlen würde es auch noch durch probieren gehen. Aber tatsächlich hab ich über 100 Objekte umzusortieren, da wär ein solcher Trick schon hilfreich.

Danke für eure Antworten.

#2

einfachste Antwort: Dann stell doch Stuhl einfach hin und parke einen neuen…

Ich kann mir nicht vorstellen, dass man „vorab“ „mal eben“ erkennt, welcher Stuhl geparkt werden muss, damit alles klappt. Ich würde sogar soweit gehen, dass es nicht immer diesen „magischen ´Stuhl“ gibt.

Gefühlt muss man durch Versuche ermitteln, ob der Algorhytmus: „Genau ein Stuhl wird geparkt“ klappt. Dann hat man den Stuhl gefunden. Würde bedeuten, dass um den Tausch Algo eine Schleife über alle Stühle kommt, die immer wieder einen anderen auswählt (von Platz1, dann 2, dann …) bis man einen gefunden hat der klappt. Klingt langsam.

Aber Frage: Willst du nur einfach nach Vorgabe sortieren können, oder geht es um „Optimierung“. Außerdem wäre es interessant, in welcher Umgebung das erfolgt. Früher habe so was in der Art mal unter TurboPascal über Pointer gemacht…

fg

Dirk_P

#3

Zunächst einmal: Dies ist Mathematik, ein spezieller Bereich der Gruppentheorie beschäftigt sich mit Permutationen.

Ein Ergebnis ist, wie Du auch richtig vorgemacht hast, daß sich jede Permutation in sog. Zykeln zerlegen läßt.

Wenn eine Permutation aus nur einem Zykel besteht, dann läßt sich Dein Parkproblem geschickt lösen, und die Lösung heißt, nimm einen (irgendeinen) Stuhl aus dem Zykel als geparkten Stuhl heraus.

Auf der anderen Seite gibt es auch Permutationen, die aus mehr als einem Zykel bestehen, bei allen solchen hast Du Pech, und es gibt keinen „ersten“ Stuhl. Als Beispiel nimm 1 2 3 4 wird zu 2 1 4 3, in Zykelschreibweise (1 2)(3 4)

Nimmst Du nun Stuhl 1 als geparkten Stuhl, so kommt nach dem Tausch von 2 und 1 sofort Dein Stop. Nimmst Du Stuhl 2, sieht es genauso aus. Nimmst Du Stuhl 3, so mußt Du 4 auf 3 stellen und es kommt Dein Stop. Du siehst, es liegt nicht am Verfahren, sondern an der Mathematik.