Permutation als Produkt von Nachbarvertauschungen |
| 18.11.2013, 10:18 | Chrilo | Auf diesen Beitrag antworten » | ||
| Permutation als Produkt von Nachbarvertauschungen ich habe folgende Aufgabe zu Lösen: Schreiben Sie die Permutation als ein Produkt von Nachbarvertauschungen und bestimmen Sie das Signum von . Ich bin noch nicht so sicher im Umgang mit Zykeln und NAchbarvertauschungen Mein Ansatz: Permutation in Transpositionen zu schreiben Könnt ihr mir schonmal bis dahin sagen ob das richtig ist? |
||||
| 20.11.2013, 21:42 | sandych33ks | Auf diesen Beitrag antworten » | ||
| Nachbarvertauschungen Hey, das erste Problem bei deiner Rechnung ist, dass du keine Nachbarvertauschungen verwendet hast, sondern lediglich Transpositionen. Bei Nachbarvertauschungen handelt es sich um Vertauschungen zweier Elemente, die, wie der Name schon sagt, Nachbarn sind, also beispielsweise: (3 4) oder (1 2). Das nächste Problem ist, dass deine Transpositionen nicht korrekt sind. Es müsste (2713)(365) = (2 3) (3 6)(5 6)(2 7)(1 7) lauten. Wenn wir das mithilfe von Nachbarvertauschungen darstellen möchten, käme bei mir (2713)(365) = (34)(23)(45)(56)(45)(34)(23)(67)(56)(45)(34)(23)(67)(56)(45)(34)(23)(12)(23 )(34)(45)(56)(67) raus. Ich hoffe das Ergebnis stimmt und du liest das noch vor Do. 14 Uhr. Mfg ein Kommilitone |
||||
| 25.11.2014, 14:36 | Stinsome | Auf diesen Beitrag antworten » | ||
| RE: Nachbarvertauschungen Hallo, ich habe momentan ein ähnliches Problem zu lösen. Kann mir vielleicht jemand erklären, wie man auf diese Darstellung mit den Nachbarvertauschungen kommt? Liebe Grüße, Stinsome |
||||
| 25.11.2014, 17:24 | HAL 9000 | Auf diesen Beitrag antworten » | ||
Wie man auf diese kommt, weiß ich nicht - ich kann dir nur sagen, wie man auf eine gültige kommt. 
Ich würde erstmal von der Zykel- zur Tupelschreibweise übergehen - dann geht es hier um als Ziel. Ausgehend von der identischen Permutation würde ich jetzt von vorn nach hinten, oder von hinten nach vorn die Elemente an die richtige Position befördern. Ich wähle mal ersteres, schiebe also zuächst die 1 nach hinten durch (12)(23)(34)(45)(56)(67), es entsteht . Nun mit (45)(56) die 5, wir sind dann bei . Und so weiter: (23)(34)(45) --> (23)(34) --> (12)(23) --> Und das war's auch schon, die letzten beiden 6,7 stehen bereits richtig. Macht alles zusammen dann (12)(23)(34)(45)(56)(67)(45)(56)(23)(34)(45)(23)(34)(12)(23) Das ist eine von vielen Möglichkeiten.
|
||||
| 26.11.2014, 16:39 | Stinsome | Auf diesen Beitrag antworten » | ||
Hallo, danke erstmal für deine Antwort, hatte sie gestern irgendwie übersehen. So an sich verstehe ich dein Vorgehen, wie aber kommst du auf die Nachbarvertauschungen? Wieso verschiebst du die 5 mit (45)(56) und die 3 mit (23)(34)(45)? Oder warum die 1 mit 6 Nachbarvertauschungen und die 4 beispielsweise nur mit 2? Das ist mir leider noch nicht so ganz klar. Ich habe die Permutation (6 4 1 5)(3 6 2 5) gegeben, die ich jetzt so umgeformt habe (bevor ich deine Antwort gelesen habe): 1 2 3 4 5 6 = (1534)(26) = (15)(13)(14)(26) 5 6 4 1 3 2 Ich habe gelesen, dass man (26) = (16)(12)(16) schreiben kann, stimmt das? Bei "Matheplanet" taucht nämlich dann diese Formel für die Nachbarvertauschungen auf: (1,i)=(i-1,i)...(2,3)(1,2)(2,3)...(i-1,i) Dann wird meine Darstellung mit den Nachbarvertauschungen aber ziemlich lang, sie soll aber kleinstmöglich sein... |
||||
| 26.11.2014, 16:43 | HAL 9000 | Auf diesen Beitrag antworten » | ||
Du musst immer im Auge behalten, wo wir nach den bereits erfolgten Permutationen gerade stehen! Was denkst du, warum sonst ich immer den Zwischenstand da angegeben habe? 
So sind wir oben nach der Positionierung der 1 bei angelangt. Nun wollen wir als nächstes die 5 auf die vorletzte, 6.Position schieben, momentan steht sie aber erst an Position 4. Also muss sie von 4 auf 6 geschoben werden, und das geschieht nun mal durch die beiden Nachbarvertauschungen (45)(56). Jetzt klar? |
||||
| Anzeige | ||||
|
|
||||
| 26.11.2014, 16:59 | Stinsome | Auf diesen Beitrag antworten » | ||
Ah! Okay, das macht natürlich Sinn. Doof von mir 
Bei mir wäre also [5, 6, 4, 1, 3, 2] das Ziel. Ich will zuerst die 2 verschieben mit (23)(34)(45)(56)(67) -> [1, 3, 4, 5, 6, 2] Als nächstes die 3 mit (23)(34)(45) -> [1, 4, 5, 6, 3, 2] Die 1 mit (12)(23)(34) -> [4, 5, 6, 1, 3, 2] Die 4 mit (12)(23) -> [5, 6, 4, 1, 3, 2] Dann habe ich mein Ziel erreicht, habe also folgende Nachbarvertauschungen: (23)(34)(45)(56)(67)(23)(34)(45)(12)(23)(34)(12)(23) Korrekt? Das ist auf jeden Fall schon mal viel kürzer, als das, was ich vorher hatte... |
||||
| 26.11.2014, 17:01 | Stinsome | Auf diesen Beitrag antworten » | ||
Das (67) muss natürlich gestrichen werden, weil ich weniger Zahlen habe... |
||||
| 26.11.2014, 17:04 | HAL 9000 | Auf diesen Beitrag antworten » | ||
Ja, so sollte es stimmen. |
||||
| 26.11.2014, 17:07 | Stinsome | Auf diesen Beitrag antworten » | ||
Vielen Dank! 
Du weißt nicht zufällig auch, ob das die kleinstmögliche Lösung ist oder es irgendeinen Trick gibt, wie man die kleinstmögliche Lösung erhält? |
||||
| 26.11.2014, 17:18 | HAL 9000 | Auf diesen Beitrag antworten » | ||
Jede Nachbarvertauschung verändert die Anzahl der Fehlstände um genau Eins nach oben oder unten. Damit ist klar, dass die Minimalzahl der Nachbarvertauschungen in dieser Darstellung gleich der Anzahl der Fehlstände der gewünschten Zielpermutation ist, in deinem Fall wäre das 12. In dem Sinne ist das Verfahren wohl optimal, allerdings ist die erzeugte Folge nicht eindeutig, es gibt auch andere optimal lange Folgen von Nachbarvertauschungen, die auf dieselbe Permutation führen (wenn wir z.B. von vorn anfangen die Zielpermutation aufzubauen). |
||||
| 26.11.2014, 17:39 | Stinsome | Auf diesen Beitrag antworten » | ||
Vielen vielen Dank! |
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
