Determinanten

mata

ja, dann gilt ja auch det = 0

Zur Leibniz Formel zurück:

Mein Ziel ist es ein kleines C++ Programm zu schreiben, dass mir den Determinantenwert mit Hilfe der Leibniz Formel berechnet.

Das Verfahren:
Ich bilde alle möglichen Permutationen. Dann muss ich für jede Permutation herausfinden, ob das vorzeichen + oder - ist. Vorzeichen ist + wenn Permutation gerade ist, und - wenn Permutation ungerade ist. Am schlusse summiere ich alle Permutationen und das Resultat ist berechnet.

Wie kann ich schnell und effektiv herausfinden ob eine Permutation gerade oder ungerade ist??
Gibt es eine Funktion, die das kann? Oder muss ich selber Hand anlegen (Implementierung krieg ich hin)?

Wie bilde ich alle Permutationen der Zahlen (1,2,...,n)? Gibt es eine Funktion, die das kann? Falls nein, wie lautet der Algorithmus?

fubar

Determinanten_11 schrieb:

Mein Ziel ist es ein kleines C++ Programm zu schreiben, dass mir den Determinantenwert mit Hilfe der Leibniz Formel berechnet.

Daß du für die Berechnung der Derterminante einer Matrix mit dem Leibniz-Verfahren jeweils n! Summanden berechnen mußt und die Formel für große n damit unbrauchbar wird, hat MaSTaH ja schon erwähnt. Falls du das nur zu Lernzwecken programmieren willst, ist das bestimmt eine gute Übung, ansonsten berechne die LU-Zerlegung der Matrix, da bekommst du die Determinante quasi geschenkt ...
[Zum Vergleich: hier werden ca. 1/3n³⁺ⁿ2-1/3n "wesentliche" Rechenop. benötigt]

Determinanten_11 schrieb:

Wie kann ich schnell und effektiv herausfinden ob eine Permutation gerade oder ungerade ist??
Gibt es eine Funktion, die das kann? Oder muss ich selber Hand anlegen

Hmm, ich wüßte so keine Fkt., die das kann.

Determinanten_11 schrieb:

Wie bilde ich alle Permutationen der Zahlen (1,2,...,n)? Gibt es eine Funktion, die das kann? Falls nein, wie lautet der Algorithmus?

http://www.sgi.com/tech/stl/next_permutation.html

mata

es gilt doch:

permutation grade: gerade anzahl fehlstände (fehlstand = p(i) > p(j) und i < j)
permutation ungrade: sonst

kann man doch recht einfach umsetzen, oder?

mata schrieb:

es gilt doch:

permutation grade: gerade anzahl fehlstände (fehlstand = p(i) > p(j) und i < j)
permutation ungrade: sonst

kann man doch recht einfach umsetzen, oder?

Klar (hab ja gesagt, dass ich das kann).

Wenns bereits eine Standard Funktion für etwas gibt, dann nehme ich diese und codiere nicht selber was Neues.

Jester

Das riecht aber nach O(n^2), weil Du jedes mit jedem Vergleichen mußt. Vielleicht könnte man das auch einfach sortieren und die Anzahl der Vertauschungen zählen... das wäre dann wenigstens O(n*log(n)).

MfG Jester

mata

man kann permutationen ja auch in zykelschreibweise schreiben:

1 2 3 4
4 3 1 2

ist dann (1423) - dieses Zykel hat 4 Stellen, gerade -> signum der Permutation -1 (sonst 1). Wenn mehrere Zykel entstehen, kann man das signum multiplizieren und erhält das signum der Permutation:

1 2 3 4
2 1 4 3

ist (12)(34) => signum = -1*-1 = 1 => Permutation gerade.

sign p =  1 => permutation grade
         -1 => permutation ungrade

damit sollte man es doch mit O(n) hinkriegen, oder täusch ich mich?

mata schrieb:

man kann permutationen ja auch in zykelschreibweise schreiben:

1 2 3 4
4 3 1 2

ist dann (1423) - dieses Zykel hat 4 Stellen, gerade -> signum der Permutation -1 (sonst 1). Wenn mehrere Zykel entstehen, kann man das signum multiplizieren und erhält das signum der Permutation:

1 2 3 4
2 1 4 3

ist (12)(34) => signum = -1*-1 = 1 => Permutation gerade.
sign p =  1 => permutation grade
         -1 => permutation ungrade
damit sollte man es doch mit O(n) hinkriegen, oder täusch ich mich?

@Masta: Dein Text hört sich sehr intelligent an. Nur verstehe ich ihn nicht ganz.
Kannst du deine Idee noch weiter ausführen oder gleich ein kleines Code Sample posten?

Jester

mata: wenn Du annimmst, daß Du die Zykelschreibweise in O(n) hinkriegst kannste das machen. Die Frage ist nur, ob das geht.

Angenommen es ginge. Ich hab hier ne beliebige Permutation. Dann würde ich die einfach in Zykelschreibweise machen O(n) und die Zykel dann möglicherweise ebenfalls mit Aufwand O(n) rückwärts ausführen. Dann hätte ich mit O(n) sortiert...

Man muß also zumindest genau nachschaun, ob das so geht. Zumindest müßtest Du noch verraten wo Du die Zykelschreibweise so schnell herkriegst.

MfG Jester

Jester schrieb:

mata: wenn Du annimmst, daß Du die Zykelschreibweise in O(n) hinkriegst kannste das machen. Die Frage ist nur, ob das geht.

Angenommen es ginge. Ich hab hier ne beliebige Permutation. Dann würde ich die einfach in Zykelschreibweise machen O(n) und die Zykel dann möglicherweise ebenfalls mit Aufwand O(n) rückwärts ausführen. Dann hätte ich mit O(n) sortiert...

Man muß also zumindest genau nachschaun, ob das so geht. Zumindest müßtest Du noch verraten wo Du die Zykelschreibweise so schnell herkriegst.

MfG Jester

Ich denke am einfachsten ist es, wenn uns masta ein kleines Code Sample postet.