TU Wien:Mathematik 1 UE (diverse)/Übungen WS10/Beispiel 136

Sei eine Permutation $\pi$ von $\{1,2,\dots ,n\}$ in zweizeiliger Darstellung gegeben. Unter der Inversionstafel von $\pi$ versteht man die Folge $(b_1,\dots ,b_n)$, wobei $b_k\ge 0$ angibt, wieviele größere Zahlen in der zweiten Zeile links vom Element k stehen. Bestimmen Sie für die Permutation $\pi$ aus Aufgabe 135 die Inversionstafel.

Wie kann man bei Kenntnis der Inversionstafel die Permutation rekonstruieren? Demonstrieren Sie ein geeignetes Verfahren am obigen Beispiel.

Lösungsvorschlag

$\pi =\left(\begin{array}{ccccccccc}1& 2& 3& 4& 5& 6& 7& 8& 9\\ 8& 9& 1& 7& 2& 5& 4& 3& 6\end{array}\right)$

Inversionstafel

Die dazugehörige Inversionstafel sieht dann so aus:

$\left(\begin{array}{ccccccccc}1& 2& 3& 4& 5& 6& 7& 8& 9\\ 1& 0& 6& 0& 4& 1& 1& 1& 0\end{array}\right)$

Rekonstruktion der Permutation

Man geht die Inversionstafel von rechts nach links durch und fügt Schritt für Schritt die nächst höhere Zahl (beginnend bei 1 ein)

Am Anfang steht immer rechts oben eine 1.

An der Inversionstafel sieht man, wieviele größere Zahlen jeweils neben der aktuellen Spalte stehen müssen.

Angenommen es wären 3, dann nimmt man die drei größten Zahlen der vorhergegangen Zeile und inkrementiert diese jeweils um eins. In die akutelle Spalte schreibt man die Zahl, die in der aktuellen Zahlenfolge noch fehlt. Alle anderen Zahlen (falls vorhanden lässt man unberührt und schreibt sie von der vorigen Zeile ab)

$\begin{array}{cccccccccc}& 1& 2& 3& 4& 5& 6& 7& 8& 9\\ 9& 0& 0& 0& 0& 0& 0& 0& 0& 1& 0& & \text{hier kann man nur mit 1 anfangen}\\ 8& 0& 0& 0& 0& 0& 0& 0& 1& 2& 1& & \text{1 inkrementieren und 1 in die 8. Spalte}\\ 7& 0& 0& 0& 0& 0& 0& 2& 1& 3& 1& & \text{2 inkrementieren und 2 in die 7. Spalte}\\ 6& 0& 0& 0& 0& 0& 3& 2& 1& 4& 1& & \text{3 inkrementieren und 3 in die 6. Spalte}\\ 5& 0& 0& 0& 0& 1& 4& 3& 2& 5& 4& & \text{1-4 inkrementieren und 1 in die 5. Spalte}\\ 4& 0& 0& 0& 6& 1& 4& 3& 2& 5& 0& & \text{es wird nur die 6 in die 4. Spalte geschrieben}\\ 3& 0& 0& 1& 7& 2& 5& 4& 3& 6& 6& & \text{1-6 inkrementieren und 1 in die 3. Spalte}\\ 2& 0& 8& 1& 7& 2& 5& 4& 3& 6& 0& & \text{es wird nur die 8 in die 2. Spalte geschrieben}\\ 1& 8& 9& 1& 7& 2& 5& 4& 3& 6& 6& & \text{8 inkrementieren und 8 in die 1. Spalte}\end{array}$

Die erste Spalte soll die Nummer der aktuellen Spalte bezeichnen

in der letzten Spalte steht die Anzahl der größeren Ziffern rechts von der aktuellen Spalte (also die Inversionstafel auf den Kopf gestellt)