TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 330

Aus VoWi
Zur Navigation springen Zur Suche springen

Sei eine Permutation von \pi von { 1, 2, ..., n } in zweizeiliger Darstellung gegeben.

Unter der Inversionstafel von \pi versteht man die Folge { b_1, b_2, ..., b_n }, wobei b_k \ge 0 angibt, wieviele größere Zahlen in der zweiten Zeile links Element k stehen. Bestimmen Sie für die Permutation \pi aus Aufgabe 119) die Inversionstafel.

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

Erstellen der Inversionstafel[Bearbeiten]

Die Permutation \pi in zweizeiliger Darstellung schaut so aus:

\pi = 
\begin{pmatrix}
 1& 2& 3& 4& 5& 6& 7& 8& 9\\
 8& 9& 1& 7& 2& 5& 4& 3& 6
\end{pmatrix}

Wenn man jetzt für jede Zahl der zweiten Zeile die Anzahl der Zahlen, die links davon und größer sind, erhält man die Inversionstafel:

  • links von 8 sind 0 Zahlen größer als 8
  • links von 9 sind 0 Zahlen größer als 9
  • links von 1 sind 2 Zahlen größer als 1 (nämlich 8 und 9)
  • .
  • .
  • links von 6 sind 3 Zahlen größer als 6 (nämlich 8, 9 und 7)

Damit erhält man als Inversionstafel:

1 2 3 4 5 6 7 8 9
0 0 2 2 3 3 4 5 3

Rekonstruieren der Permutation[Bearbeiten]

Zum Rekonstruieren der Permutation aus der Inversionstafel sucht man nacheinander jeweils das kleinste Element der Permutation. Das kleinste Element ist am Anfang die 1. Hat man die 1 gefunden, kann man die Spalte der 1 ignorieren und das neue kleinste Element ist die 2, usw.

Das kleinste Element hat die Eigenschaft, dass alle Elemente die links davon stehen größer sind (Oh Mann, wer hätte das gedacht *g*).

Angenommen das kleinste Element steht an der Stelle k, so gilt immer:

b_k = k-1

Steht das kleinste Element z.B. an der 5. Stelle, dann steht in der Inversionstafel an der 5. Stelle der Wert 4.

Gibt es in der Inversionstafel zwei Elemente b_j und b_k mit 1 \le j < k \le n und b_j = j-1, b_k = k-1, so ist immer das Element rechts (hier b_k) das kleinste Element.

Wäre b_j da kleinste Element, gäbe es links von b_k ein Element das kleiner ist, und somit könnte b_k nur noch eine Wert von maximal k-2 haben, und nicht k-1.

Unten ist der Lösungsweg Schritt-für-Schritt ausgeführt. Die fettgedruckten Zahlen in der Inversionstafel sind die "möglichen" Positionen für das kleinste Element (sie erfüllen b_k = k-1), jeweils das Element rechts ist die richtige Position des kleinesten Elements. Die bereits verwendeten Positionen werden in den nachfolgenden Schritten ignoriert.

kleinstes Element Inversionstafel Permutation
1
1 2 3 4 5 6 7 8 9
0 0 2 2 3 3 4 5 3
 
\begin{pmatrix}
 1& 2& 3& 4& 5& 6& 7& 8& 9\\
 & & 1& & & & & & 
\end{pmatrix}
2
1 2 4 5 6 7 8 9
0 0 2 3 3 4 5 3
 
\begin{pmatrix}
 1& 2& 3& 4& 5& 6& 7& 8& 9\\
 & & 1& & 2& & & & 
\end{pmatrix}
3
1 2 4 6 7 8 9
0 0 2 3 4 5 3
 
\begin{pmatrix}
 1& 2& 3& 4& 5& 6& 7& 8& 9\\
 & & 1& & 2& & & 3& 
\end{pmatrix}
4
1 2 4 6 7 9
0 0 2 3 4 3
 
\begin{pmatrix}
 1& 2& 3& 4& 5& 6& 7& 8& 9\\
 & & 1& & 2& & 4& 3& 
\end{pmatrix}
5
1 2 4 6 9
0 0 2 3 3
 
\begin{pmatrix}
 1& 2& 3& 4& 5& 6& 7& 8& 9\\
 & & 1& & 2& 5& 4& 3& 
\end{pmatrix}
6
1 2 4 9
0 0 2 3
 
\begin{pmatrix}
 1& 2& 3& 4& 5& 6& 7& 8& 9\\
 & & 1& & 2& 5& 4& 3& 6
\end{pmatrix}
7
1 2 4
0 0 2
 
\begin{pmatrix}
 1& 2& 3& 4& 5& 6& 7& 8& 9\\
 & & 1& 7& 2& 5& 4& 3& 6
\end{pmatrix}
8
1 2
0 0
 
\begin{pmatrix}
 1& 2& 3& 4& 5& 6& 7& 8& 9\\
 8& & 1& 7& 2& 5& 4& 3& 6
\end{pmatrix}
9
2
0
 
\begin{pmatrix}
 1& 2& 3& 4& 5& 6& 7& 8& 9\\
 8& 9& 1& 7& 2& 5& 4& 3& 6
\end{pmatrix}

mfg, --W wallner