Diskussion:Fehlstand

Und wie berechnet man nun diese Inversionstafel?

Konkretes Beispiel: Aus den Permutationen der Zahlen von 1…16 – also alle von (1,2,3,…,14,15,16) bis (16,15,14,…,3,2,1) – habe ich die folgende Permutation vor mir liegen: (6,10,4,3,9,12,5,11,14,8,3,1,7,13,15,2). Die wievielte ist das nun und wie berechnet man das am einfachsten? --RokerHRO (Diskussion) 10:41, 19. Aug. 2015 (CEST)

Wo ist das Problem, das steht alles im Artikel, sogar mit Beispielen. Im Abschnitt "Inversionstafel" steht wie man sie berechnet: Du fängst mit der 1 an und zählst wie viele größere Zahlen links von der 1 stehen, das sind 11. Diese Zahl trägst du als erste Komponente ein. Das gleiche machst du mit der 2, der 3 und so weiter und erhältst so am Ende

$I(\pi )=(11,14,3,\ldots )$.

Die Nummer der Permutation ermittelst du dann mit der Formel im Abschnitt "Aufzählung von Permutationen":

$z(\pi )=11\cdot 15!+14\cdot 14!+3\cdot 13!+\ldots$.

Viele Grüße, --Quartl (Diskussion) 11:05, 19. Aug. 2015 (CEST)

Ich hab halt die angegebene Formel

$b_{j}=\#\left\{i\in \{1,\ldots ,n\}\mid (\pi ^{-1}(i),\pi ^{-1}(j))\in \operatorname {inv} (\pi )\right\}$

nicht verstanden und dann aufgegeben. :-(

Ich muss also für jede gegebene Permutation diese Inversionstafel von neuem berechnen? Ich muss also bei n-elementigen Permutationen n-mal über die Liste iterieren, also n*n/2 Vergleiche anstellen, um erstmal die Inversionstafel zu bekommen, und dann jedes Element der Inversionstafel mit den (vorberechneten) Fakultäten von n! bis 0! multiplizieren? Hm… Klingt rechenaufwändig, wenn ich das richtig verstanden habe. Kann man das nicht mit geschickten vorausberechneten Lookup-Tabellen irgendwie vereinfachen? :-( --RokerHRO (Diskussion) 11:12, 19. Aug. 2015 (CEST)

Die Fragen hatte ich alle schon in Diskussion:Permutation#n-te Permutation beantwortet ;-). Die Berechnung der Inversionstafel geht bei geschickter Implementierung auch in $O(n\log n)$ statt $O(n^{2})$. Bei einer gegebenen Permutation geht es nicht schneller, außer du arbeitest alle $n!$ Permutationen in einer besonderen Reihenfolge ab. Viele Grüße, --Quartl (Diskussion) 11:32, 19. Aug. 2015 (CEST)

Ich kenne die alten Diskussionen. Hab deine Antwort aber leider schon damals nicht verstanden, wie diese "geschickte Implementierung" aussehen soll, die auf O(n·log n) kommt. Ist auch die Frage, ob sich das für n=16 überhaupt lohnt.

Die Permutationen, deren Nummer/Position ich ermitteln will, sind leider nicht aufeinanderfolgend, sondern recht wüst verstreut. :-(

--RokerHRO (Diskussion) 12:16, 19. Aug. 2015 (CEST)

Der Algorithmus steht im Knuth (TAOCP, Band 3). Ob sich die Mühe lohnt hängt von den Konstanten in der Landau-Notation ab. Bei n=16 ist das im Idealfall eine Verbesserung um einen Faktor 4. Viele Grüße, --Quartl (Diskussion) 13:16, 19. Aug. 2015 (CEST)

Hah, funktioniert! :-)

Ich habs erst mit der von dir gegebenen Formel für die Inversionen gemacht, aber ich finde den "Lehmer-Code" besser, da er der lexikographischen Reihenfolge entspricht:

Permutation	Lehmer-Code	Fehlstands-Nr
(0, 1, 2, 3)	(0, 0, 0, 0)	0
(0, 1, 3, 2)	(0, 0, 1, 0)	1
(0, 2, 1, 3)	(0, 1, 0, 0)	2
(0, 2, 3, 1)	(0, 1, 1, 0)	3
(0, 3, 1, 2)	(0, 2, 0, 0)	4
(0, 3, 2, 1)	(0, 2, 1, 0)	5
(1, 0, 2, 3)	(1, 0, 0, 0)	6
(1, 0, 3, 2)	(1, 0, 1, 0)	7
(1, 2, 0, 3)	(1, 1, 0, 0)	8
(1, 2, 3, 0)	(1, 1, 1, 0)	9
(1, 3, 0, 2)	(1, 2, 0, 0)	10
(1, 3, 2, 0)	(1, 2, 1, 0)	11
(2, 0, 1, 3)	(2, 0, 0, 0)	12
(2, 0, 3, 1)	(2, 0, 1, 0)	13
(2, 1, 0, 3)	(2, 1, 0, 0)	14
(2, 1, 3, 0)	(2, 1, 1, 0)	15
(2, 3, 0, 1)	(2, 2, 0, 0)	16
(2, 3, 1, 0)	(2, 2, 1, 0)	17
(3, 0, 1, 2)	(3, 0, 0, 0)	18
(3, 0, 2, 1)	(3, 0, 1, 0)	19
(3, 1, 0, 2)	(3, 1, 0, 0)	20
(3, 1, 2, 0)	(3, 1, 1, 0)	21
(3, 2, 0, 1)	(3, 2, 0, 0)	22
(3, 2, 1, 0)	(3, 2, 1, 0)	23

Danke nochmal! :-) --RokerHRO (Diskussion) 15:21, 26. Aug. 2015 (CEST)