Nachbartranspositionen < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 09:06 Mo 28.08.2006 | | Autor: | garfieldxxs |
Kennt hier jemand einen einfachen Weg oder irgendein Prinzip/Schema, wie man eine Permutation als Produkt benachbarter Transpositionen schreiben kann?
Wäre wirklich dankbar für eine Hilfe! Danke! 
|
|
| |
|
Hallo und guten Morgen,
geh von der Identität aus und lasse dann jede Zahl i - von 1 beginnend zB - an ihre neue Position [mm] \pi(i) [/mm] wandern, durch Transpostionen
kannst Du eine solche Wanderung beschreiben.
Ob das dann die kleinste Zahl von Transpositionen in einer solchen Darstellung ergibt, ist eine andere Frage.
Das ist noch nicht die richtige Antwort, da Du dann ja beim Wandern mit 2 evtl. nicht zum letzten Wanderschritt von 1benachbart bist. Dies koenntest
Du ueberbrücken durch ''Verbindungsketten'' von Transpositionen und ihren Inversen.
Anderer Ansatz:
Geh mit ner ''Sweep Line'' durch die Permutation hin und her, und wenn Du ein Paar benachbarter Zahlen i,j hast, so dass momentan i links von j steht, am Ende aber j links von i stehen soll, so vertauscht Du sie, ansonsten vertauscht Du sie zweimal. Hat wieder diesen unschönen Beigeschmack, dass dann evtl die Darstellung die Gestalt [mm] \ldots \tau\circ\tau\ldots [/mm] hat.
Du kannst dann jedenfalls argumentieren, dass sich bei diesem Verfahren die Zahl der Fehlstellungen stets verringert, solange noch welche existieren, und in [mm] O(n^2) [/mm] Schritten terminiert das Verfahren.
Zu dem Fall, dass Du [mm] \ldots \tau\circ\tau\ldots [/mm] nicht zulassen willst, hab ich noch nicht die passende Antwort.
Gruss,
Mathias
|
|
|
| |
|
Danke für die Antwort... aber...
ähhh... was um alles in der Welt ist eine "sweep line"??? noch nie gehört!!
Hilfe - das versteh ich mal beim besten Willen überhaupt nicht...
Gibt es dazu zufälig irgendwo ein Beispiel, wo ich mir das erst einmal daran klar machen könnte?
Gruß, garfield
|
|
|
| |
|
Mist, ich kriegs echt nicht hin... Bitte helft mir doch nochmal :-(
Das Zeug macht mich langsam wahnsinnig...
Wäre echt super, wenn da jemand ein Prinzip dazu hätte...
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 12:20 Do 31.08.2006 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
