kombinatorische Algorithmen

Blatt 2 SS00

Prof. Laue

Abgabe 17.05.2000 in der Vorlesung

 

 

Aufgabe 3  (3+5+3 Punkte)


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?