In der Vorlesung wurde der Johnson Trotter Algorithmus vorgestellt.
Um die Menge der Permutationen Sn zu durchlaufen war es nötig
zusätzlich die Bewegungsrichtung der Zahlen 1 bis n zu speichern.
Dies kann man umgehen, indem man die Permutation mittels Trottercode kodiert.
Dies ist eine n Elemente lange Zahlenfolge (c0, c1,...,cn-1)
wobei für den Eintrag ci gilt:
0 <= ci <= i
mit folgender Interpretation kann ich aus dem Code wieder eine Permutation erlangen:
ci ist die Anzahl der kleineren Zahlen rechts von i+1 falls
c0+c1+....ci-1 gerade.
ci ist die Anzahl der kleineren Zahlen links von i+1 falls
c0+c1+....ci-1 ungerade.
Konstruieren Sie die Permutation zum Code 0,1,1,3,3,2.
Zeigen Sie, daß der lexikographische Durchlauf durch die möglichen Codes dem Durchlauf mittels Johnson Trotter entspricht.
Wie kann man mittels dieser Kodierung eine Rangfunktion angeben?