Algorithmus - Zyklus als Transposition schreiben

• Involvierte Definitionen:
  • Zyklus
  • Transposition
• Veranstaltung: AlMa
• Referenz: } AlgoMathe KE1 - Abbildungen, Permutationen, Fakultät

⠀

Proposition: Zyklus als Transposition schreiben

Wir können einen Zyklus in Transpositionen splitten, in dem wir Zyklen wie folgt bilden:

• Erste Zahl des Zyklus festhalten
• Und dann von rechts nach links, also:

Anmerkung

Und wofür ist das gut?

Nun, manche Aussagen über Permutationen lassen sich einfacher durch Divide and Conquer beweisen, indem man sie in Transpositionen aufspaltet.